Pagini recente » Cod sursa (job #2001782) | Cod sursa (job #2127514) | Cod sursa (job #2066443) | Cod sursa (job #738354) | Cod sursa (job #1320247)
#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 ;
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 == N ){
q = pref[q];
++Answer ;
if ( Answer <= 1000 )
Sol[Answer] = i - N ;
}
}
}
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] << " ";
in.close();
out.close();
return 0 ;
}