Pagini recente » Cod sursa (job #661492) | Cod sursa (job #1601924) | Cod sursa (job #1892458) | Cod sursa (job #292337) | Cod sursa (job #397233)
Cod sursa(job #397233)
#include<cstdio>
#include<cstring>
#define max 2000005
char P[max],T[max];
int U[max],sol[1001],nr,m,n;
void prefix(){
int i,k;
for( i=1, k=-1, U[0]=-1; i < m; i++){
while( k>0 && P[ k+1 ] != P[i] ) k = U[k];
if( P[k+1] == P[i] ) k++;
U[i]=k;
}
}
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 x,i;
for( i=0, x=-1; i<n;i++){
while( x>0 && P[ x+1 ] != T[i] ) x = U[x];
if( P[ x+1 ] == T[i] ) x++;
if ( x == m-1 ){
if( ++nr < 1001 ) sol[nr] = i-m+1;
x = U[x];
}
}
fprintf(g,"%d\n",nr);
nr = nr>1000?1000:nr;
for(i=1;i<=nr;i++) fprintf(g,"%d ",sol[i]);
return 0;
}