Pagini recente » Cod sursa (job #492520) | Cod sursa (job #1750841) | Cod sursa (job #241417) | Cod sursa (job #280106) | Cod sursa (job #2322226)
#include <bits/stdc++.h>
char a[2000002], b[2000002];
int sol[2000000], pi[2000001];
int main(){
FILE *fin, *fout;
int i, lc, n=1, m=1, nsol=0;
fin=fopen("strmatch.in", "r");
fout=fopen("strmatch.out", "w");
b[1]=fgetc(fin);
while(b[n]!='\n')
b[++n]=fgetc(fin);
a[1]=fgetc(fin);
while(a[m]!='\n')
a[++m]=fgetc(fin);
n--;
m--;
pi[1]=0;
lc=0;
for(i=2;i<=n;i++){
while(lc>0 && b[i]!=b[lc+1])
lc=pi[lc];
if(b[i]==b[lc+1])
lc++;
pi[i]=lc;
}
//for(i=1;i<=n;i++)
//printf("%d ", pi[i]);
//printf("\n");
lc=0;
for(i=1;i<=m;i++){
while(lc>0 && a[i]!=b[lc+1])
lc=pi[lc];
if(a[i]==b[lc+1])
lc++;
//printf("lc: %d\n", lc);
if(lc==n)
sol[nsol++]=i;
}
fprintf(fout, "%d\n", nsol);
for(i=0;i<nsol && i<1000;i++)
fprintf(fout, "%d ", sol[i]-n);
fclose(fin);
fclose(fout);
return 0;
}