Pagini recente » Istoria paginii runda/e | Cod sursa (job #770481) | Borderou de evaluare (job #1036392) | Istoria paginii runda/simulare_oji | Cod sursa (job #738567)
Cod sursa(job #738567)
#include<cstdio>
#include<cstring>
#define dim 2000005
char a[dim],b[dim];
int n,m,sol[1005],contor,pref[dim];
void prefix(){
int i,k;
for(i=1;i<=n;i++){
k=pref[i-1];
while(k>0 && a[i]!=a[k]) k=pref[k-1];
if(a[i]==a[k]){
k++;
pref[i]=k;
}
}
}
void kmp(){
int i,k=0;
for(i=0;i<=m;i++){
while(k>0 && a[k]!=b[i]) k=pref[k-1];
if(a[k]==b[i])
k++;
if(k==n+1){
++contor;
if(contor<=1000)
sol[contor]=i-k+1;
}
}
}
int main(){
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
fgets(a,dim,stdin);
fgets(b,dim,stdin);
n=strlen(a)-2; m=strlen(b)-2;
prefix(); kmp();
printf("%d\n",contor);
for(int i=1;i<=(contor<1000?contor:1000);i++)
printf("%d ",sol[i]);
}