Pagini recente » Cod sursa (job #1064854) | Cod sursa (job #2895586) | Cod sursa (job #1097479) | Cod sursa (job #2141628) | Cod sursa (job #1264649)
#include <fstream>
#include <cstring>
#define IN "strmatch.in"
#define OUT "strmatch.out"
const int MAX = 2000014 ;
const int P = 71 ;
const int MOD1 = 236013 ;
const int MOD2 = 256017 ;
using namespace std;
ifstream fin ( IN ) ;
ofstream fout ( OUT ) ;
char A [ MAX ] , B [ MAX ] ;
int ans [ MAX ] ;
int main()
{
int NA , NB , SMALLHASH1 = 0 , BIGHASH1 = 0 , SMALLHASH2 = 0 , BIGHASH2 = 0 , PUTMAX1 = 1 , PUTMAX2 = 1 ;
fin >> A ;
fin >> B ;
NA = strlen ( A ) ;
NB = strlen ( B ) ;
if ( NA > NB ){
fout << "0" ;
return 0 ;
}
for ( register int i = 0 ; i < NA ; ++ i ){
SMALLHASH1 = ( SMALLHASH1 * P + A [ i ] ) % MOD1 ;
SMALLHASH2 = ( SMALLHASH2 * P + A [ i ] ) % MOD2 ;
if ( i ){
PUTMAX1 = ( PUTMAX1 * P ) % MOD1 ;
PUTMAX2 = ( PUTMAX2 * P ) % MOD2 ;
}
}
int sol = 0 ;
for ( register int i = 0 ; i < NA ; ++ i ){
BIGHASH1 = ( BIGHASH1 * P + B [ i ] ) % MOD1 ;
BIGHASH2 = ( BIGHASH2 * P + B [ i ] ) % MOD2 ;
}
if ( BIGHASH1 == SMALLHASH1 and BIGHASH2 == SMALLHASH2 )
ans [ 0 ] = 1 ;
for ( register int i = NA ; i <= NB ; ++ i ){
BIGHASH1 = ( ( ( ( BIGHASH1 - B [ i - NA ] * PUTMAX1 ) % MOD1 + MOD1 ) * P ) + B [ i ] ) % MOD1 ;
BIGHASH2 = ( ( ( ( BIGHASH2 - B [ i - NA ] * PUTMAX2 ) % MOD2 + MOD2 ) * P ) + B [ i ] ) % MOD2 ;
if ( BIGHASH1 == SMALLHASH1 and BIGHASH2 == SMALLHASH2 ){
ans [ i - NA + 1 ] = 1 ;
sol ++ ;
}
}
fout << sol << '\n' ;
sol = 1 ;
for ( register int i = 0 ; i <= MAX and sol <= 1000 ; ++i )
if ( ans [ i ] ){
fout << i << " " ;
sol ++ ;
}
return 0 ;
}