Pagini recente » Cod sursa (job #2745582) | Cod sursa (job #3216465) | Cod sursa (job #219381) | Cod sursa (job #2340923) | Cod sursa (job #2545511)
#include <cmath>
#include <vector>
#include <fstream>
#include <iostream>
using namespace std ;
string inp1 , inp2 ;
inline long long fast_pow ( int x , int y , int mod )
{
if ( y == 1 ) return x ;
long long p = x , ans = 1 ;
while ( y )
{
if ( y & 1 )
ans = ( ans * p ) % mod ;
p = ( p * p ) % mod ;
y = ( y >> 1 ) ;
}
return ans ;
}
struct hash_pair
{
long long hash1 , hash2 , BASE , MOD , INV_MOD , p ;
void hardcode ( long long a , long long b )
{
BASE = a ;
MOD = b ;
INV_MOD = fast_pow ( BASE , MOD - 2 , MOD ) ;
}
} ;
hash_pair hash_array [ 10 ] ;
int nr = 0 ;
vector < long long > v ;
inline int ok ( void )
{
for ( int i = 1 ; i <= nr ; ++ i )
if ( hash_array [ i ].hash1 != hash_array [ i ].hash2 )
return 0 ;
return 1 ;
}
int main ()
{
ifstream in ( "strmatch.in" ) ;
ofstream out ( "strmatch.out" ) ;
int i , j ;
nr = 2 ;
hash_array [ 1 ].hardcode ( 1e4 + 39 , 1e9 + 9 ) ;
hash_array [ 2 ].hardcode ( 1e4 + 61 , pow ( 2 , 31 ) - 1 ) ;
in >> inp1 >> inp2 ;
if ( inp1.size () > inp2.size () )
{
out << "0" ;
return 0 ;
}
for ( i = 1 ; i <= nr ; ++ i )
hash_array [ i ].p = 1 ;
for ( i = 0 ; i < inp1.size () ; ++ i )
for ( j = 1 ; j <= nr ; ++ j )
{
hash_array [ j ].hash1 = ( hash_array [ j ].hash1 + inp1 [ i ] * hash_array [ j ].p ) % hash_array [ j ].MOD ;
hash_array [ j ].hash2 = ( hash_array [ j ].hash2 + inp2 [ i ] * hash_array [ j ].p ) % hash_array [ j ].MOD ;
hash_array [ j ].p = ( hash_array [ j ].p * hash_array [ j ].BASE ) % hash_array [ j ].MOD ;
}
for ( i = 1 ; i <= nr ; ++ i )
hash_array [ i ].p = fast_pow ( hash_array [ i ].BASE , inp1.size () - 1 , hash_array [ i ].MOD ) ;
if ( ok () )
v.push_back ( 0 ) ;
for ( i = 1 ; i < inp2.size () - inp1.size () + 1 ; ++ i )
{
for ( j = 1 ; j <= nr ; ++ j )
{
hash_array [ j ].hash2 = ( hash_array [ j ].hash2 + hash_array [ j ].MOD - inp2 [ i - 1 ] ) % hash_array [ j ].MOD ;
hash_array [ j ].hash2 = ( hash_array [ j ].hash2 * hash_array [ j ].INV_MOD ) % hash_array [ j ].MOD ;
hash_array [ j ].hash2 = ( hash_array [ j ].hash2 + inp2 [ i + inp1.size () - 1 ] * hash_array [ j ].p ) % hash_array [ j ].MOD ;
}
if ( ok () )
v.push_back ( i ) ;
}
out << v.size () << '\n' ;
for ( i = 0 ; i < v.size () ; ++ i )
out << v [ i ] << ' ' ;
return 0 ;
}