Pagini recente » Cod sursa (job #13585) | Cod sursa (job #559601) | Cod sursa (job #2181363) | Cod sursa (job #1357239) | Cod sursa (job #3277766)
#include <fstream>
#include <vector>
#include <string>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int BASE_1 = 97;
const int BASE_2 = 101;
const int MOD_1 = 666013;
const int MOD_2 = 1000033;
long long MAX_EXPONENT_1 = 1;
long long MAX_EXPONENT_2 = 1;
string a, b;
long long hasher(const string &number, int BASE, int MOD){
long long hashed_number = 0;
long long exponent = 1;
for (int i = a.size() - 1; i >= 0; i--){
hashed_number += (number[i] - 'A') * exponent;
exponent *= BASE;
exponent %= MOD;
hashed_number = hashed_number % MOD;
}
return hashed_number;
}
void solve(){
fin >> a >> b;
for (int i = 1; i < a.size(); i++){
MAX_EXPONENT_1 *= BASE_1;
MAX_EXPONENT_1 %= MOD_1;
MAX_EXPONENT_2 *= BASE_2;
MAX_EXPONENT_2 %= MOD_2;
}
long long hash_1_a = hasher(a, BASE_1, MOD_1);
long long hash_2_a = hasher(a, BASE_2, MOD_2);
// fout << hash_1_a << " " << hash_2_a << '\n';
long long hash_1_b = hasher(b, BASE_1, MOD_1);
long long hash_2_b = hasher(b, BASE_2, MOD_2);
// fout << '\n';
// fout << 0 << " " << hash_1_b << " " << hash_2_b << '\n';
int to_delete = 0;
vector<int> occurences;
for (int i = a.size(); i < b.size(); i++){
hash_1_b = (((((((hash_1_b - (MAX_EXPONENT_1 * (b[to_delete] - 'A'))) % MOD_1) + MOD_1) % MOD_1) * BASE_1)
% MOD_1) + b[i] - 'A' % MOD_1) % MOD_1;
hash_2_b = (((((((hash_2_b - (MAX_EXPONENT_2 * (b[to_delete] - 'A'))) % MOD_2) + MOD_2) % MOD_2) * BASE_2)
% MOD_2) + b[i] - 'A' % MOD_2) % MOD_2;
to_delete++;
// fout << to_delete << " " << hash_1_b << " " << hash_2_b << '\n';
if (hash_1_a == hash_1_b && hash_2_a == hash_2_b) {
occurences.push_back(to_delete);
}
}
fout << occurences.size() << '\n';
for (int p = 0; p < occurences.size() && p <= 999; p++){
fout << occurences[p] << " ";
}
}
int main(){
solve();
return 0;
}