Pagini recente » Cod sursa (job #2616366) | Cod sursa (job #374604) | Cod sursa (job #1897566) | Cod sursa (job #2735268) | Cod sursa (job #1043784)
#include <stdio.h>
#include <string.h>
#define fr(i,a,b) for(int i=a;i<b;++i)
#define N 2000000
#define P 1000
char s[N+1],w[N+1];
int t[N],p[P];
int main(){
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%[^\n]s",w);
scanf("\n");
scanf("%[^\n]s",s);
int pos=2,cnd=0;
int wl=strlen(w),sl=strlen(s);
t[0]=-1,t[1]=0;
while(pos<wl){
if(w[pos-1]==w[cnd]) t[pos]=++cnd,++pos;
else if(cnd) cnd=t[cnd];
else t[pos]=0,++pos;
}
int m=0,i=0;
int pl=-1,pt=0;
while(m+i<sl){
if(w[i]==s[m+i]){
++pt;
if(i==wl-1) {
if(pl<P-1)p[++pl]=m;
m+=i-t[i];
i=(t[i]>-1)?t[i]:0;
}
else ++i;
}
else{
m+=i-t[i];
i=(t[i]>-1)?t[i]:0;
}
}
printf("%i\n",pt);
++pl;
fr(i,0,pl)printf("%i ",p[i]);
return 0;
}