Pagini recente » Cod sursa (job #877444) | Cod sursa (job #2150732) | Cod sursa (job #2031197) | Cod sursa (job #530512) | Cod sursa (job #1219568)
#include <cstring>
#include <cstdio>
#define maxN 2000013
char S1[maxN], S2[maxN];
int Pi[maxN], d[maxN];
int i,k(0),A,B,sol(0);
void build_pi()
{
int k(0),N(strlen(S1)-1),i;
Pi[1]=0;
for (i=2;i<=N;++i){
while (k>0 && S1[i]!=S1[k+1]) k=Pi[k];
if (S1[i]==S1[k+1]) ++k;
Pi[i]=k;
}
}
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
fgets(S1+1,maxN,stdin);
fgets(S2+1,maxN,stdin);
S1[0]=S2[0]=' ';
S1[strlen(S1)-1]=S2[strlen(S2)-1]=0;
A=strlen(S1)-1;
B=strlen(S2)-1;
build_pi();
for (i=1;i<=B;++i){
while (k>0 && S2[i]!=S1[k+1]) k=Pi[k];
if (S2[i]==S1[k+1]) ++k;
if (k==A){
k=Pi[A];
++sol;
if (sol<=1000) d[sol]=i-A;
}
}
printf("%d\n",sol);
for (i=1;i<=sol;++i)
printf("%d ",d[i]);
return 0;
}