Pagini recente » Cod sursa (job #144985) | Cod sursa (job #1089040) | Cod sursa (job #3004953) | Cod sursa (job #172030) | Cod sursa (job #3162129)
#include <bits/stdc++.h>
using namespace std;
const int BAZA = 73;
const int MOD1 = 666013;
const int MOD2 = 511111;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
string A, B;
int modif( int Hash, int i, int put, int mod ){
Hash = ( Hash + mod - ( put * (int)B[i - (int)A.size()]) % mod ) % mod;
Hash = ( Hash * BAZA + (int)B[i]) % mod;
return Hash;
}
int main()
{
int Ahash1, Ahash2, Bhash1, Bhash2, put1 = 1, put2 = 1;
vector <int> sol;
in >> A >> B;
if( A.size() == B.size()){
out << 0;
return 0;
}
Ahash1 = Ahash2 = Bhash1 = Bhash2 = 0;
for( int i = 0; i < A.size(); i++ ){
Ahash1 = (Ahash1 * BAZA + (int)A[i]) % MOD1;
Ahash2 = (Ahash2 * BAZA + (int)A[i]) % MOD2;
if( i ){
put1 = ( put1 * BAZA ) % MOD1;
put2 = ( put2 * BAZA ) % MOD2;
}
}
for( int i = 0; i < A.size(); i++ ){
Bhash1 = (Bhash1 * BAZA + (int)B[i]) % MOD1;
Bhash2 = (Bhash2 * BAZA + (int)B[i]) % MOD2;
}
if( Ahash1 == Bhash1 && Ahash2 == Bhash2)
sol.push_back(0);
for( int i = A.size(); i < B.size(); i++ ){
Bhash1 = modif( Bhash1, i, put1, MOD1);
Bhash2 = modif( Bhash2, i, put2, MOD2);
if( Ahash1 == Bhash1 && Ahash2 == Bhash2)
sol.push_back(i-A.size()+1);
}
out << sol.size() << "\n";
int k = sol.size();
if( k > 1000 )
k = 1000;
for( int i = 0; i < k; i++ )
out << sol[i] << " ";
return 0;
}