Pagini recente » Cod sursa (job #366264) | Cod sursa (job #2246962) | Cod sursa (job #3239236) | Cod sursa (job #2718557) | Cod sursa (job #2545612)
#include <cmath>
#include <vector>
#include <fstream>
#include <iostream>
using namespace std ;
const long long MOD1 = 1e9 + 7 ;
const long long MOD2 = 1e9 + 9 ;
const long long BASE = 91 ;
vector < int > v ;
inline long long fast_pow ( long long x , long long y , long long mod )
{
long long ans = 1 , p = x ;
while ( y )
{
if ( y & 1 )
ans = ( ans * p ) % mod ;
p = ( p * p ) % mod ;
y = ( y >> 1 ) ;
}
return ans ;
}
int main ()
{
ifstream in ( "strmatch.in" ) ;
ofstream out ( "strmatch.out" ) ;
string inp1 , inp2 ;
long long hash11 , hash12 , hash21 , hash22 ;
long long i , n , m , inv1 , inv2 , pwr1 , pwr2 ;
in >> inp1 >> inp2 ;
n = inp1.size () ;
m = inp2.size () ;
if ( n > m )
{
out << 0 ;
return 0 ;
}
inv1 = fast_pow ( BASE , MOD1 - 2 , MOD1 ) ;
inv2 = fast_pow ( BASE , MOD2 - 2 , MOD2 ) ;
hash11 = hash12 = hash21 = hash22 = 0 ; pwr1 = pwr2 = 1 ;
for ( i = 0 ; i < n ; ++ i )
{
hash11 = ( hash11 + ( pwr1 * 1LL * inp1 [ i ] ) % MOD1 ) % MOD1 ;
hash21 = ( hash21 + ( pwr1 * 1LL * inp2 [ i ] ) % MOD1 ) % MOD1 ;
pwr1 = ( pwr1 * BASE ) % MOD1 ;
hash12 = ( hash12 + ( pwr2 * 1LL * inp1 [ i ] ) % MOD2 ) % MOD2 ;
hash22 = ( hash22 + ( pwr2 * 1LL * inp2 [ i ] ) % MOD2 ) % MOD2 ;
pwr2 = ( pwr2 * BASE ) % MOD2 ;
}
if ( hash11 == hash21 && hash12 == hash22 )
v.push_back ( 0 ) ;
pwr1 = fast_pow ( BASE , n - 1 , MOD1 ) ;
pwr2 = fast_pow ( BASE , n - 1 , MOD2 ) ;
for ( i = n ; i < m ; ++ i )
{
hash21 = ( hash21 + MOD1 - inp2 [ i - n ] ) % MOD1 ;
hash21 = ( hash21 * inv1 ) % MOD1 ;
hash21 = ( hash21 + ( 1LL * inp2 [ i ] * pwr1 ) % MOD1 ) % MOD1 ;
hash22 = ( hash22 + MOD2 - inp2 [ i - n ] ) % MOD2 ;
hash22 = ( hash22 * inv2 ) % MOD2 ;
hash22 = ( hash22 + ( 1LL * inp2 [ i ] * pwr2 ) % MOD2 ) % MOD2 ;
if ( hash11 == hash21 && hash12 == hash22 && v.size () < 1000 )
v.push_back ( i - n + 1 ) ;
}
out << v.size () << '\n' ;
for ( i = 0 ; i < v.size () ; ++ i )
out << v [ i ] << ' ' ;
return 0 ;
}