Pagini recente » Cod sursa (job #2302996) | Cod sursa (job #799248) | Cod sursa (job #2288669) | Cod sursa (job #629684) | Cod sursa (job #213227)
Cod sursa(job #213227)
#include<stdio.h>
#include<algorithm>
using namespace std;
char a[2000111],b[2000111];
int N,sol[2000111],n,m,i,q,pi[1024];
int min(int a,int b){
if(a<b)
return a;
return b;
}
int main(){
FILE *f=fopen("strmatch.in","r");
FILE *g=fopen("strmatch.out","w");
fscanf(f,"%s",a+1);
fscanf(f,"%s",b+1);
q=pi[1]=0;
a[0]=b[0]=' ';
n=strlen(a);
m=strlen(b);
n--;
m--;
for(i=2;i<=n;i++){
while(q && a[q+1]!=a[i])
q=pi[q];
if(a[q+1] == a[i] )
q++;
pi[i]=q;
}
q=0;
for(i=1;i<=m;i++){
while(q && a[q+1] != b[i])
q=pi[q];
if(a[q+1] == b[i])
q++;
if(q==n){
q=pi[q];
N++;
sol[N]=i-n;
}
}
fprintf(g,"%d\n",N);
for(i=1;i<=min(N,1000);i++)
fprintf(g,"%d ",sol[i]);
fclose(f);
fclose(g);
return 0;
}