Pagini recente » Cod sursa (job #425732) | Cod sursa (job #1994239) | Cod sursa (job #1744765) | Cod sursa (job #2738981) | Cod sursa (job #392335)
Cod sursa(job #392335)
#include<cstdio>
#include<string.h>
#define max 2000005
int n,m,pre[max],sol[1001];
char P[max],T[max];
void Prefix(){
int i,x;
for( i=1, x=-1; i<=m;i++){
while( x > 0 && P[ x+1 ] != P[ i ]) x = pre[x];
if( P[ x+1 ] == P [i] ) x++;
pre[i] = x;
}
}
int main(){
FILE *f=fopen("strmatch.in","r");
FILE *g=fopen("strmatch.out","w");
fscanf(f,"%s\n%s",P,T);
m = strlen(P);
n = strlen(T);
Prefix();
int i,x,k=0;
x=-1;
for( i=0; i<=n;i++){
while( x>0 && P [ x+1 ] != T [i] ) x = pre[x];
if( P[ x+1 ] == T [i] ) x++;
if( x == m-1 ){
k++;
if( k<1001 ) sol[k] = i - m + 1;
x = pre[x];
}
}
fprintf(g,"%d\n",k);
k = k>1000?1000:k;
for(i=1;i<=k;i++) fprintf(g,"%d ",sol[i]);
return 0;
}