Pagini recente » Cod sursa (job #1918526) | Cod sursa (job #2069954) | Cod sursa (job #2434904) | Cod sursa (job #77256) | Cod sursa (job #3159507)
#include <bits/stdc++.h>
using namespace std;
const int BAZA = 37;
const int MOD1 = 666013;
const int MOD2 = 511111;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
string A, B;
int n, hsh1, hsh2, m;
void hashuri( string &X ){
hsh1 = 0, hsh2 = 0, m = n;
while( m > 0 ){
hsh1 = (hsh1 * BAZA + X[m] - 'A') % MOD1;
hsh2 = (hsh2 * BAZA + X[m] - 'A') % MOD2;
m--;
}
}
int Putere( int a , int x , int mod ){
if( x == 0 )
return 1;
if( x % 2 == 1)
return (a * Putere(a , x - 1, mod)) % mod;
int P = Putere(a , x / 2, mod) % mod;
return ((1ll)P * P)% mod;
}
int modif( int Hash, int i, int put, int mod ){
Hash -= put * B[i-n-1];
if( put * B[i-n-1] > Hash )
Hash = ( Hash + mod - put * B[i-n-1] ) % mod;
Hash = (Hash + B[i] ) % mod;
return Hash;
}
int main()
{
int rez = 0;
vector <int> sol;
cin >> A >> B;
n = A.size()-1;
hashuri(A);
int Ahash1 = hsh1, Ahash2 = hsh2;
hashuri(B);
int Bhash1 = hsh1, Bhash2 = hsh2;
int put1 = Putere( BAZA, n, MOD1);
int put2 = Putere( BAZA, n, MOD2);
if( Ahash1 == Bhash1 && Ahash2 == Bhash2){
rez++;
sol.push_back(0);
}
for( int i = n+1; i < B.size(); i++ ){
Bhash1 = modif( Bhash1, i, put1, MOD1);
Bhash2 = modif( Bhash2, i, put2, MOD2);
if( Ahash1 == Bhash1 && Ahash2 == Bhash2){
rez++;
sol.push_back(i);
}
}
out << rez << "\n";
int k = sol.size();
if( k > 1000 )
k = 1000;
for( int i = 0; i < k; i++ )
out << i << " ";
return 0;
}