Pagini recente » Cod sursa (job #688619) | Cod sursa (job #1936107) | Cod sursa (job #67439) | Cod sursa (job #1598818) | Cod sursa (job #1533165)
#include <cstdio>
#include <algorithm>
#define nmax 2000005
#include <cstring>
using namespace std;
void read();
void make_prefix();
void kmp();
char a[nmax],b[nmax];
int pi[nmax],pos[1024];
int m,n,res;
int main(){
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
read();
make_prefix();
kmp();
printf("%d\n",res);
for(int i=1;i<=min(res,1000);++i)printf("%d ",pos[i]);
printf("\n");
return 0;
}
void read(){
scanf("%s ",a);m=strlen(a)-1;
scanf("%s ",b);n=strlen(b)-1;
}
void make_prefix(){
int i,q=0;
for(i=2,pi[1]=0;i<m;i++){
while(q && a[q+1]!=a[i])q=pi[q];
if(a[q+1]==a[i])++q;
pi[i]=q;
}
}
void kmp(){
int q=0,i;
res=0;
for(i=1;i<n;i++){
while(q && a[q+1]!=b[i])q=pi[q];
if(a[q+1]==b[i])++q;
if(q==m){
q=pi[m];
++res;
if(res<=1000)pos[res]=i-m;
}
}
}