Pagini recente » Profil coxs | Monitorul de evaluare | Cod sursa (job #2068896) | Cod sursa (job #2147089) | Cod sursa (job #302607)
Cod sursa(job #302607)
#include<stdio.h>
#include<string.h>
#define NM 2000001
char t[NM],p[NM];
int u[NM],n,m,s[1001];
void urm(){
int q,k=-1;
u[0]=-1;
for(q=1;q<m;++q){
while(k>-1&&p[k+1]!=p[q])
k=u[k];
if(p[k+1]==p[q]) k++;
u[q]=k;
}
}
int main(){
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s\n%s",p,t);
int i,ok,k=0,q;
m=strlen(p);
n=strlen(t);
urm();
q=-1;
for(i=0;i<n-m+1;++i){
while(q>-1&&p[q+1]!=t[i]) q=u[q];
if(p[q+1]==t[i]) q++;
if(q==m-1) {
k++;
if(k<=1000) s[k]=i-m+1;
q=u[q];
}
}
printf("%d\n",k);
for(i=1;i<=k&&i<=1000;++i) printf("%d ",s[i]);
return 0;
}