Pagini recente » Cod sursa (job #424284) | Cod sursa (job #880281) | Cod sursa (job #2788607) | Cod sursa (job #2279716) | Cod sursa (job #1437865)
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
#define Nmax 2000002
FILE *f = fopen ( "strmatch.in", "r" );
FILE *g = fopen ( "strmatch.out", "w" );
char A[Nmax], B[Nmax];
int Pi[Nmax], N, M, nrMatch;
vector < int > sol;
void Prefix (){
int k = 0;
for ( int i = 2; i <= N; ++i ){
while ( k > 0 && A[k+1] != A[i] )
k = Pi[k];
if ( A[k+1] == A[i] )
k++;
Pi[i] = k;
}
}
void Match(){
int k = 0;
for ( int i = 1; i <= M; ++i ){
while ( k > 0 && A[k+1] != B[i] )
k = Pi[k];
if ( A[k+1] == B[i] )
k++;
if ( k == N ){
nrMatch++;
if ( nrMatch <= 1000 )
sol.push_back( i - N );
}
}
}
int main(){
vector < int > :: iterator it;
fscanf ( f, "%s%*c", A + 1 );
fscanf ( f, "%s", B + 1 );
N = strlen ( A + 1 );
M = strlen ( B + 1 );
if ( N > M ){
fprintf ( g, "0" );
return 0;
}
Prefix ();
Match();
fprintf ( g, "%d\n", nrMatch );
for ( it = sol.begin(); it < sol.end(); ++it )
fprintf ( g, "%d ", *it );
return 0;
}