Pagini recente » Cod sursa (job #1705726) | Cod sursa (job #1908966) | Cod sursa (job #1442617) | Borderou de evaluare (job #1394086) | Cod sursa (job #1257387)
/*
* Code by Spiromanul
*/
#include <fstream>
#include <cstring>
#include <bitset>
const char IN [ ] = "strmatch.in" ;
const char OUT [ ] = "strmatch.out" ;
const int MAX = 2000014 ;
const int MOD1 = 299777 ;
const int MOD2 = 299771 ;
const int Bb = 71 ;
using namespace std;
ifstream fin ( IN ) ;
ofstream fout ( OUT ) ;
char A [ MAX ] , B [ MAX ] ;
bitset < MAX > ANS ;
int main( )
{
fin >> A ;
fin >> B ;
int NA = strlen ( A ) ;
int NB = strlen ( B ) ;
int SMALLHASH1 = 0 ;
int SMALLHASH2 = 0 ;
int PUTMAX1 = 1 ;
int PUTMAX2 = 1 ;
for ( int i = 0 ; i < NA ; ++ i )
{
SMALLHASH1 = ( SMALLHASH1 * Bb + A [ i ] ) % MOD1 ;
SMALLHASH2 = ( SMALLHASH2 * Bb + A [ i ] ) % MOD2 ;
if ( i )
PUTMAX1 = ( PUTMAX1 * Bb ) % MOD1 ,
PUTMAX2 = ( PUTMAX2 * Bb ) % MOD2 ;
}
if ( NA > NB )
{
fout << 0 << '\n' ;
return 0 ;
}
int BIGHASH1 = 0 ;
int BIGHASH2 = 0 ;
for ( int i = 0 ; i < NA ; ++ i )
BIGHASH1 = ( BIGHASH1 * Bb + B [ i ] ) % MOD1 ,
BIGHASH2 = ( BIGHASH2 * Bb + B [ i ] ) % MOD2 ;
int SOL = 0 ;
if ( SMALLHASH1 == BIGHASH1 and SMALLHASH2 == BIGHASH2 )
{
ANS [ 0 ] = 1 ;
++ SOL ;
}
for ( int i = NA ; i < NB ; ++ i )
{
BIGHASH1 = ( ( ( BIGHASH1 - B [ i - NA ] * PUTMAX1 ) % MOD1 + MOD1 ) * Bb + B [ i ] ) % MOD1 ;
BIGHASH2 = ( ( ( BIGHASH2 - B [ i - NA ] * PUTMAX2 ) % MOD2 + MOD2 ) * Bb + B [ i ] ) % MOD2 ;
if ( SMALLHASH1 == BIGHASH1 and SMALLHASH2 == BIGHASH2 )
{
ANS [ i - NA + 1 ] = 1 ;
++ SOL ;
}
}
// afisare
fout << SOL << '\n' ;
SOL = 0 ;
for ( int i = 0 ; i < NB and SOL <= 1000 ; ++ i )
if ( ANS [ i ] )
{
fout << i << ' ' ;
++ SOL ;
}
fout << '\n' ;
return 0;
}