Pagini recente » Cod sursa (job #1849029) | Rating Cretu Aurelia (Aurelia) | Cod sursa (job #2737569) | Cod sursa (job #2252674) | Cod sursa (job #157007)
Cod sursa(job #157007)
#include <cstring>
#include <cstdio>
const int nmax=2000001;
char a[nmax],b[nmax];
int pi[nmax],poz[1001],n,m;
void prefix(){
int i,k;
pi[0]=-1;pi[1]=0;
for (i=2,k=0;i<=n;i++) {
while (k>0 && a[i-1]!=a[k]) k=pi[k];
if (a[i-1]==a[k]) k++;
pi[i]=k;}
}
void search(){
int i,k;
for (i=0,k=0;i+k<m;){
if (a[k]==b[i+k]){k++;
if (k==n) {poz[0]++;
if (poz[0]<=1000) poz[poz[0]]=i;
i=i+n-pi[n];
k=pi[n];}
}
else {i=i+k-pi[k];
if (k>0) k=pi[k];}
}
}
int main(){
int i;
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s\n%s",a,b);
n=strlen(a);
m=strlen(b);
prefix();
search();
printf("%d\n",poz[0]);
if (poz[0]>1000) poz[0]=1000;
for (i=1;i<=poz[0];i++) printf("%d ",poz[i]);
fclose(stdout);
}