Pagini recente » Cod sursa (job #1286801) | Arhiva de probleme | Cod sursa (job #3197999) | Cod sursa (job #600186) | Cod sursa (job #1494008)
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXPOS 1000
char a[2000011], b[2000011];
int pi[2000011], pos[MAXPOS];
int main()
{
FILE *fin, *fout;
int n, m, k, p, i;
fin=fopen("strmatch.in", "r");
fgets(a+1, 2000010, fin);
n=strlen(a+1);
fgets(b+1, 2000010, fin);
m=strlen(b+1);
fclose(fin);
--n; --m;
k=0;
for(i=2; i<=n; i++){
while(k && a[k+1]!=a[i])
k=pi[k];
if(a[k+1]==a[i])
++k;
pi[i]=k;
}
p=k=0;
fout=fopen("strmatch.out", "w");
for(i=1; i<=m; i++){
while(k && a[k+1]!=b[i])
k=pi[k];
if(a[k+1]==b[i])
++k;
if(k==n){
if(p<MAXPOS)
pos[p]=i-n;
++p;
}
}
fprintf(fout, "%d\n", p);
p=p<=1000?p:1000;
for(i=0; i<p; i++)
fprintf(fout, "%d ", pos[i]);
fprintf(fout, "\n");
fclose(fout);
return 0;
}