Pagini recente » Cod sursa (job #471292) | Cod sursa (job #1157976) | Cod sursa (job #1890828) | Cod sursa (job #112176) | Cod sursa (job #2372066)
#include <bits/stdc++.h>
using namespace std;
#define LMAX 2000005
char s[LMAX],t[LMAX];
int n,m,p[LMAX];
void make_prefix(){
int q=0;
p[1]=0;
for(int i=2;i<=n;++i){
while(q>0&&s[q+1]!=s[i])
q=p[q];
if(s[q+1]==s[i])
++q;
p[i]=q;
}
}
int poz[1005];
void match(){
int q=0;
for(int i=1;i<=m;++i){
while(q>0&&s[q+1]!=t[i])
q=p[q];
if(s[q+1]==t[i])
++q;
if(q==n){
++poz[0];
if(poz[0]<=1000)
poz[poz[0]]=i-n;
q=p[q];
}
}
printf("%d\n",poz[0]);
for(int i=1;i<=min(1000,poz[0]);++i)
printf("%d ",poz[i]);
}
int main(){
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s",s+1);
n=strlen(s+1);
make_prefix();
scanf("%s",t+1);
m=strlen(t+1);
match();
return 0;
}