Pagini recente » Cod sursa (job #493985) | civilizatie | Cod sursa (job #2488252) | Cod sursa (job #174539) | Cod sursa (job #392341)
Cod sursa(job #392341)
#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, pre[0]=0; 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[m-1];
}
}
fprintf(g,"%d\n",k);
k = k>1000?1000:k;
for(i=1;i<=k;i++) fprintf(g,"%d ",sol[i]);
return 0;
}