Pagini recente » Cod sursa (job #3162483) | Cod sursa (job #2953061) | Cod sursa (job #2600942) | Cod sursa (job #1047965) | Cod sursa (job #169905)
Cod sursa(job #169905)
#include<stdio.h>
#include<string.h>
#define lg 2000010
char s1[lg],s2[lg],sir1[lg],sir2[lg];
int n,m,pr[lg],rez[1001],rezultat;
void prefix(){
int k,i;
k=0;
for(i=2;i<=n;++i){
while(k>0 && sir1[k+1]!=sir1[i])
k=pr[k];
if(sir1[k+1]==sir1[i])
++k;
pr[i]=k;
}
}
int main(){
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
int i,k;
scanf("%s%s",s1,s2);
n=strlen(s1);
m=strlen(s2);
for(i=0;i<n;++i)
sir1[i+1]=s1[i];
for(i=0;i<m;++i)
sir2[i+1]=s2[i];
prefix();
k=0;
for(i=1;i<=m;++i){
while(k>0 && sir1[k+1]!=sir2[i])
k=pr[k];
if(sir1[k+1]==sir2[i])
++k;
if(k==n){
++rezultat;
if(rezultat<=1000)
rez[rezultat]=i-n;
}
}
printf("%d\n",rezultat);
if(rezultat>1000){
for(i=1;i<1000;++i)
printf("%d ",rez[i]);
printf("%d\n",rez[i]);
}
else{
if(rezultat){
for(i=1;i<rezultat;++i)
printf("%d ",rez[i]);
printf("%d\n",rez[rezultat]);
}
}
fclose(stdin);
fclose(stdout);
return 0;
}