Pagini recente » Cod sursa (job #588931) | Cod sursa (job #560107) | Cod sursa (job #2266358) | Cod sursa (job #1249370) | Cod sursa (job #1320243)
#include <fstream>
#include <algorithm>
#include <vector>
#include <cstring>
#define NMAX 2000005
#define get_max(a,b) ((a)>(b)?(a):(b))
using namespace std;
ifstream in ( "strmatch.in" );
ofstream out ( "strmatch.out" );
char sir1[NMAX] , sir2[NMAX];
int N , M , Answer , Sol[NMAX] ;
int pref[NMAX];
void KMP ( void ) {
int i , j , q = 0 ;
pref[1] = 0 ;
for ( i = 2 ; i <= N ; ++i ){
while ( q and sir1[q+1]!= sir1[i] )
q = pref[q];
if ( sir1[q+1] == sir1[i])
++q;
pref[i] = q ;
}
for ( i = 1 , q = 0 ; i <= M ; ++i ){
while ( q and sir1[q+1]!= sir2[i])
q = pref[q];
if ( sir1[q+1] == sir2[i] )
++q;
if ( q == M ){
q = pref[q];
++Answer ;
if ( Answer <= 1000 )
Sol[Answer] = i - M ;
}
}
}
int main ( void ){
int i , j ;
sir1[0] = sir2[0] = ' ';
in >> (sir1 +1 ) >> ( sir2 +1 );
N = strlen(sir1) - 1 ;
M = strlen(sir2) - 1 ;
KMP();
out << Answer << "\n";
for ( i = 1 ; i <= Answer ; ++i )
out << Sol[i] << "\n";
in.close();
out.close();
return 0 ;
}