Pagini recente » Cod sursa (job #2178130) | Cod sursa (job #1144520) | Cod sursa (job #1591110) | Cod sursa (job #2045823) | Cod sursa (job #1129309)
# include <iostream>
# include <fstream>
# include <string.h>
# define nmax 2000010
using namespace std;
ifstream f("strmatch.in");
char a[nmax], b[nmax];
int na, nb, L[nmax];
void pref()
{
int k, p;
L[0]=0;
k=0;
for(p=1; p<na; p++)
{
k=L[p-1];
while(k>0 && a[k]!=a[p])
k=L[k-1];
if(a[k]==a[p])
k+=1;
L[p]=k;
}
}
void kmp()
{
int p,k=0,nr=0,sol[1000];
fstream g("strmatch.out", ios::out);
for(p=0; p<nb; p++)
{
while(k>0 && a[k]!=b[p])
k=L[k-1];
if(b[p]==a[k])
k+=1;
if(k==na)
{
nr+=1;
if(nr<=1000)
sol[nr]=p-na+1;
k=L[k-1];
}
}
g<<nr<<'\n';
for(int i=1; i<=min(1000, nr); i++)
g<<sol[i]<<" ";
g.close();
}
int main()
{
f.getline(a,nmax);
f.getline(b,nmax);
na=strlen(a);
nb=strlen(b);
pref();
kmp();
return 0;
}