Pagini recente » Cod sursa (job #855261) | Cod sursa (job #2065698) | Cod sursa (job #440766) | Cod sursa (job #702643) | Cod sursa (job #169912)
Cod sursa(job #169912)
#include<stdio.h>
#include<string.h>
int main () {
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
char a[200000],b[200000];
int m,n,i,k=0,pi[10000],v[100000],q=0;
fgets(a+1,200000,stdin);
fgets(b+1,200000,stdin);
n=strlen(a+1);
m=strlen(b+1);
--n;--m;
pi[0]=0;
pi[1]=0;
for(i=2;i<=n;++i){
while((k>0)&&(a[k+1]!=a[i]))
k=pi[k];
if(a[k+1]==a[i])
++k;
pi[i]=k;
}
k=0;
for(i=1;i<=m;++i){
while((k>0)&&(a[k+1]!=b[i]))
k=pi[k];
if(a[k+1]==b[i])
++k;
if(k==n)
v[q++]=i-n;
}
printf("%d\n",q);
if(q){
for(i=0;i<q-1&&i<1000;++i)
printf("%d ",v[i]);
printf("\n");
}
return 0;
}