Pagini recente » Cod sursa (job #2600497) | Cod sursa (job #681230) | Cod sursa (job #1840405) | Monitorul de evaluare | Cod sursa (job #2545469)
#include <cmath>
#include <vector>
#include <fstream>
#include <iostream>
using namespace std;
const int BASE = 1031 ;
const int MOD = pow ( 2 , 31 ) - 1 ;
vector < int > v ;
inline int 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 ;
}
int main()
{
ifstream in ( "strmatch.in" ) ;
ofstream out ( "strmatch.out" ) ;
string inp1 , inp2 ;
long long hash1 = 0 , hash2 = 0 , p , inv = fast_pow ( BASE , MOD - 2 , MOD ) , i ;
in >> inp1 >> inp2 ;
if ( inp1.size () > inp2.size () )
{
out << "0" << '\n' ;
return 0 ;
}
p = 1 ;
for ( i = 0 ; i < inp1.size () ; ++ i )
{
hash1 = ( hash1 + p * inp1 [ i ] ) % MOD ;
hash2 = ( hash2 + p * inp2 [ i ] ) % MOD ;
p = ( p * BASE ) % MOD ;
}
p = fast_pow ( BASE , inp1.size () - 1 , MOD ) ;
if ( hash1 == hash2 )
v.push_back ( 0 ) ;
for ( i = 1 ; i < inp2.size () ; ++ i )
{
hash2 -= inp2 [ i - 1 ] ;
if ( hash2 < 0 ) hash2 += MOD ;
hash2 = ( hash2 * inv ) % MOD ;
hash2 = ( hash2 + p * inp2 [ i + inp1.size () - 1 ] ) % MOD ;
if ( hash2 == hash1 && v.size () < 1000 )
v.push_back ( i ) ;
}
out << v.size () << '\n' ;
for ( i = 0 ; i < v.size () ; ++ i )
out << v [ i ] << ' ' ;
return 0;
}