Pagini recente » Cod sursa (job #1134153) | Cod sursa (job #2841230) | Cod sursa (job #1805114) | Cod sursa (job #1594837) | Cod sursa (job #574353)
Cod sursa(job #574353)
#include<stdio.h>
#include<string>
#define maxL 2000005
FILE*f=fopen("strmatch.in","r");
FILE*g=fopen("strmatch.out","w");
int N,M,k,i,pi[maxL],NrSol,Sol[maxL];
char A[maxL],B[maxL];
int main () {
fscanf(f,"%s%s",A+1,B+1);
M = strlen(A+1); N = strlen(B+1);
for ( i = 2 ; i <= M ; ++i ){
while ( k > 0 && A[k+1] != A[i] )
k = pi[k];
if ( A[k+1] == A[i] )
++k;
pi[i] = k;
}
for ( i = 1 , k = 0 ; i <= N ; ++i ){
while ( k > 0 && A[k+1] != B[i] )
k = pi[k];
if ( A[k+1] == B[i] )
++k;
if ( k == M ){
k = pi[M];
++NrSol;
if ( NrSol <= 1000 )
Sol[NrSol] = i - M;
}
}
fprintf(g,"%d\n",NrSol);
if ( NrSol > 1000 ) NrSol = 1000;
for ( i = 1 ; i <= NrSol ; ++i )
fprintf(g,"%d ",Sol[i]);
fclose(f);
fclose(g);
return 0;
}