Pagini recente » Cod sursa (job #1304897) | Cod sursa (job #839206) | Cod sursa (job #394350) | Monitorul de evaluare | Cod sursa (job #2545533)
#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 ;
int main ()
{
ifstream in ( "strmatch.in" ) ;
ofstream out ( "strmatch.out" ) ;
int i , j , mod , pwr , base , n , m , ok ;
nr = 2 ;
hash_array [ 1 ].hardcode ( 1e4 + 39 , 1e9 + 9 ) ;
hash_array [ 2 ].hardcode ( 1e4 + 61 , pow ( 2 , 31 ) - 1 ) ;
in >> inp1 >> inp2 ;
n = inp1.size () ;
m = inp2.size () ;
if ( n > m )
{
out << "0" ;
return 0 ;
}
for ( i = 1 ; i <= nr ; ++ i )
hash_array [ i ].p = 1 ;
for ( i = 0 ; i < n ; ++ i )
for ( j = 1 ; j <= nr ; ++ j )
{
mod = hash_array [ j ].MOD ; pwr = hash_array [ j ].p ; base = hash_array [ j ].BASE ;
hash_array [ j ].hash1 = ( hash_array [ j ].hash1 + ( 1LL * inp1 [ i ] * pwr ) % mod ) % mod ;
hash_array [ j ].hash2 = ( hash_array [ j ].hash2 + ( 1LL * inp2 [ i ] * pwr ) % mod ) % mod ;
pwr = ( pwr * base ) % mod ;
hash_array [ j ].p = pwr ;
}
for ( i = 1 ; i <= nr ; ++ i )
hash_array [ i ].p = fast_pow ( hash_array [ i ].BASE , n - 1 , hash_array [ i ].MOD ) ;
ok = 1 ;
for ( i = 1 ; i <= nr ; ++ i )
if ( hash_array [ i ].hash1 != hash_array [ i ].hash2 )
{
ok = 0 ;
break ;
}
if ( ok ) v.push_back ( 0 ) ;
for ( i = 1 ; i < m - n + 1 ; ++ i )
{
ok = 1 ;
for ( j = 1 ; j <= nr ; ++ j )
{
mod = hash_array [ j ].MOD ; base = hash_array [ j ].BASE ; pwr = hash_array [ j ].p ;
hash_array [ j ].hash2 = ( hash_array [ j ].hash2 + mod - inp2 [ i - 1 ] ) % mod ;
hash_array [ j ].hash2 = ( hash_array [ j ].hash2 * hash_array [ j ].INV_MOD ) % mod ;
hash_array [ j ].hash2 = ( hash_array [ j ].hash2 + ( 1LL * inp2 [ i + n - 1 ] * pwr ) % mod ) % mod ;
if ( hash_array [ j ].hash1 != hash_array [ j ].hash2 )
ok = 0 ;
}
if ( ok && v.size () < 1000 )
v.push_back ( i ) ;
}
out << v.size () << '\n' ;
for ( i = 0 ; i < v.size () ; ++ i )
out << v [ i ] << ' ' ;
return 0 ;
}