Pagini recente » Cod sursa (job #596406) | Cod sursa (job #102246) | Cod sursa (job #2759615) | Cod sursa (job #582542) | Cod sursa (job #1533169)
#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;
}
}
}