Pagini recente » Cod sursa (job #1942583) | Cod sursa (job #709369) | Cod sursa (job #2794315) | Cod sursa (job #2183258) | Cod sursa (job #1320251)
#include <fstream>
#include <algorithm>
#include <vector>
#include <cstring>
#define NMAX 2000005
#define get_min(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 <= get_min(Answer, 1000) ; ++i )
out << Sol[i] << " ";
in.close();
out.close();
return 0 ;
}