Pagini recente » Cod sursa (job #2584781) | Cod sursa (job #2295741) | Cod sursa (job #796751) | Cod sursa (job #369014) | Cod sursa (job #1533105)
#include <stdio.h>
#include <stdlib.h>
#define MAXN 2000001
char v1[MAXN], v2[MAXN];
int x[MAXN], ret[MAXN];
int main(){
FILE*fin=fopen("strmatch.in", "r");
FILE*fout=fopen("strmatch.out", "w");
int n, i, k, c, m, nr, q, kmp, j;
c=fgetc(fin);
n=0;
while(c!='\n'){
n++;
v1[n]=c;
c=fgetc(fin);
}
c=fgetc(fin);
m=0;
while(c!='\n' && c!=EOF){
m++;
v2[m]=c;
c=fgetc(fin);
}
x[1]=0;
for(i=2; i<=n; i++){
if(v1[i]==v1[x[i-1]+1])
x[i]=x[i-1]+1;
else{
j=i-1;
while(j>1 && v1[x[j]+1]!=v1[i])
j=x[j];
x[i]=x[j]+1;
if((j==0 || j==1) && v1[1]!=v1[i])
x[i]=0;
}
}
kmp=nr=0;
for(i=1; i<=m; i++){
while(v2[i]!=v1[kmp+1] && kmp!=0)
kmp=x[kmp];
if(v2[i]==v1[kmp+1])
kmp++;
if(kmp==n){
if(nr<1000)
ret[nr]=i-kmp;
nr++;
}
}
fprintf(fout, "%d\n", nr);
if(nr>1000)
nr=1000;
for(i=0; i<nr; i++)
fprintf(fout, "%d ", ret[i]);
return 0;
}