Pagini recente » Cod sursa (job #3290587) | Cod sursa (job #2913592) | Cod sursa (job #714419) | Cod sursa (job #1369816) | Cod sursa (job #3162108)
#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;
void hashuri( string &X ){
hsh1 = 0, hsh2 = 0;
for( int i = 0; i < A.size(); i++ ){
hsh1 = (hsh1 * BAZA + X[i] - 'A'+1) % MOD1;
hsh2 = (hsh2 * BAZA + X[i] - 'A'+1) % MOD2;
}
}
int Putere( int a , int x , int mod ){
if( x == 0 )
return 1;
if( x % 2 == 1)
return ((long long)a * Putere(a , x - 1, mod)) % mod;
int P = Putere(a , x / 2, mod) % mod;
return ((long long)P * P)% mod;
}
int modif( int Hash, int i, int put, int mod ){
Hash = ( Hash + mod - put * ( B[i-n] - 'A' + 1 ) ) % mod;
Hash = ( Hash * BAZA + B[i] - 'A' + 1) % mod;
return Hash;
}
int main()
{
int rez = 0;
vector <int> sol;
in >> A >> B;
n = A.size();
hashuri(A);
int Ahash1 = hsh1, Ahash2 = hsh2;
hashuri(B);
int Bhash1 = hsh1, Bhash2 = hsh2;
int put1 = Putere( BAZA, n-1, MOD1);
int put2 = Putere( BAZA, n-1, MOD2);
if( Ahash1 == Bhash1 && Ahash2 == Bhash2){
rez++;
sol.push_back(0);
}
for( int i = n; 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-n+1);
}
}
out << rez << "\n";
int k = sol.size();
if( k > 1000 )
k = 1000;
for( int i = 0; i < k; i++ )
out << sol[i] << " ";
return 0;
}