Pagini recente » Cod sursa (job #2334520) | Cod sursa (job #2362628) | Cod sursa (job #2223951) | Cod sursa (job #2324809) | Cod sursa (job #1552549)
#include <cstdio>
#include <cstring>
using namespace std;
int phi[2000005],v[2000005],i,k,n,m,nr1;
char a[2000005],b[2000005];
int kmp(char a[2000005], char b[2000005],int n, int m, int v[2000005])
{
a[n+2]=' ';
phi[1]=0;
for (i=2; i<=n; i++)
{
k=phi[i-1];
while (a[i]!=a[k+1] && k>0) k=phi[k];
if (a[i]==a[k+1]) phi[i]=k+1;
else phi[i]=0;
}
for (i=1; i<=m; i++)
{
k=v[i-1];
while (k>0 && b[i]!=a[k+1]) k=phi[k];
if (b[i]==a[k+1]) v[i]=k+1;
else v[i]=0;
}
int nr=0;
for (i=1; i<=m; i++) if (v[i]==n) nr++;
return nr;
}
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
gets(a+1);
gets(b+1);
n=strlen(a+1);
m=strlen(b+1);
printf("%d\n",kmp(a,b,n,m,v));
nr1=0;
for (i=1; i<=m; i++) if (v[i]==n && nr1<1000) {printf("%d ",i-n); nr1++;}
return 0;
}