Pagini recente » Cod sursa (job #3163822) | Cod sursa (job #2125515) | Cod sursa (job #546230) | Cod sursa (job #1407389) | Cod sursa (job #704333)
Cod sursa(job #704333)
#include <fstream>
#include <cstring>
using namespace std;
#define nmax 2000002
int urm[nmax];
char T[nmax], P[nmax];
int n, m, qq;
bool here[nmax];
void citire()
{
ifstream in("strmatch.in");
in>>P>>T;
n = strlen(T); m = strlen(P);
}
void afisare()
{
ofstream out("strmatch.out");
//for(int k=0; k<m; k++)
//out<<urm[k]<<" ";
out<<qq<<"\n";
if(qq > 1000)
qq = 1000;
for(int i=0; i<n && qq; i++)
if(here[i])
{
out<<i<<" ";
qq--;
}
}
void urmatorul( char p[])
{
int i, x=-1;
urm[0] = 0;
for(i=1; i<m; i++)
{
while(x>0 && p[x+1]!=p[i])
x = urm[x];
if(p[x+1] == p[i])
x++;
urm[i] = x;
}
}
void kmp()
{
int i, x=-1;
for(i=0; i<n; i++)
{
while(x>0 && P[x+1]!=T[i])
x = urm[x];
if(P[x+1] == T[i])
x++;
if(x == m-1)
{
here[i-m+1] = true;
qq++;
//out<<i-m+1<<"\n";
x = urm[x];
}
}
}
int main()
{
citire();
urmatorul(P);
kmp();
afisare();
return 0;
}