Pagini recente » Cod sursa (job #787913) | Cod sursa (job #1059646) | Cod sursa (job #5167) | Cod sursa (job #1686628) | Cod sursa (job #1552524)
#include <cstdio>
#include <cstring>
using namespace std;
int phi[2000001],v[2000001],i,k,n,m,nr1;
char a[2000001],b[2000001];
int kmp(char a[2000001], char b[2000001],int n, int m, int v[2000001])
{
a[n+1]=' ';
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;
}