Pagini recente » Cod sursa (job #561380) | Cod sursa (job #1878296) | Cod sursa (job #2879833) | Cod sursa (job #1052587) | Cod sursa (job #176949)
Cod sursa(job #176949)
#include <stdio.h>
#include <string.h>
#define MIN( a, b ) ( (a) < (b) ) ? (a) : (b)
#define NMAX 2000001
#define SOLMAX 1001
#define FIN "strmatch.in"
#define FOUT "strmatch.out"
int PI[NMAX];
char A[NMAX], B[NMAX];
int SOL[SOLMAX];
int N, M, nr;
FILE * fin, * fout;
void build_PI()
{
int i, k = 0;
PI[1] = 0;
for( i = 2; i <= N; i++ )
{
while( A[i] != A[k+1] && k > 0 ) k = PI[k];
if( A[i] == A[k+1]) k++;
PI[i] = k;
}
}
void KMP()
{
int i, k = 0;
for( i = 1; i <= M; i++ )
{
while( B[i] != A[k+1] && k > 0 ) k = PI[k];
if( B[i] == A[k+1] ) k++;
if( k == N )
{
nr++;
if ( nr <= 1000 ) SOL[nr] = i - N;
k = PI[k];
}
}
}
int main()
{
fin = fopen( FIN, "r" );
fout = fopen( FOUT, "w" );
fscanf( fin, "%s\n", A+1 );
fscanf( fin, "%s\n", B + 1 );
N = strlen( A + 1 );
M = strlen( B + 1 );
build_PI();
KMP();
fprintf( fout, "%d\n", nr );
int t = MIN( nr, 1000 );
for( int i = 1; i <= t; i++ )
fprintf( fout, "%d ", SOL[i] );
fprintf( fout, "\n");
return 0;
}