Pagini recente » Cod sursa (job #2672166) | Cod sursa (job #121770) | Cod sursa (job #2399367) | Cod sursa (job #1215761) | Cod sursa (job #1659759)
#include <cstdio>
#include<cstring>
using namespace std;
long i,h,n,m,p;
long pi[2000012],v[1024];
char s1[2000012],s2[2000012];
void prefix()
{ int p=0;
for(i=2;i<=n;i++)
{ while(p&&s1[i]!=s1[p+1]) p=pi[p];
if(s1[i]==s1[p+1]) p++;
pi[i]=p;
}
}
void kmp()
{ p=0;h=0;
prefix();
for( i=1;i<=m;i++)
{ while(p&&s2[i]!=s1[p+1]) p=pi[p];
if(s2[i]==s1[p+1]) p++;
if(p==n) {h++;p=pi[p];if(h<=1000)v[h]=i-n;}
}
}
int main()
{ freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
fgets(s1+1,2000010,stdin);
fgets(s2+1,2000010,stdin);
n=strlen(s1+1)-1;
m=strlen(s2+1)-1;
kmp();
printf("%ld\n",h);
if(h>1000) h=1000;
for(i=1;i<=h;i++)
printf("%ld ",v[i]);
return 0;
}