Pagini recente » Cod sursa (job #2708104) | Cod sursa (job #51151) | Cod sursa (job #599356) | Cod sursa (job #2329293) | Cod sursa (job #2747623)
#include <iostream>
#include <fstream>
#include <string>
#include <algorithm>
const int MOD1 = 100007;
const int MOD2 = 100013;
const int BASE = 73;
const int MAX_AP = 1e3;
std::string a, b;
int cnt_ap;
int ap[1 + MAX_AP];
int main() {
std::ifstream in("strmatch.in");
std::ofstream out("strmatch.out");
in >> a >> b;
b = (char)('Z' + 1) + b;
int hash_a1 = 0;
int hash_a2 = 0;
for (char i : a) {
hash_a1 = (hash_a1 * BASE + (i - 'A')) % MOD1;
hash_a2 = (hash_a2 * BASE + (i - 'A')) % MOD2;
}
int hash_b1 = 0;
int hash_b2 = 0;
for (int i = 0; i < a.size(); ++i) {
hash_b1 = (hash_b1 * BASE + (b[i] - 'A')) % MOD1;
hash_b2 = (hash_b2 * BASE + (b[i] - 'A')) % MOD2;
}
int power1 = 1;
int power2 = 1;
for (int i = 1; i < a.size(); ++i) {
power1 = (power1 * BASE) % MOD1;
power2 = (power2 * BASE) % MOD2;
}
for (int i = (int)a.size(); i < b.size(); ++i) {
hash_b1 = ((hash_b1 - power1 * (b[i - (int)a.size()] - 'A') + MOD1) * BASE + (b[i] - 'A')) % MOD1;
hash_b2 = ((hash_b2 - power2 * (b[i - (int)a.size()] - 'A') + MOD2) * BASE + (b[i] - 'A')) % MOD2;
if (hash_b1 == hash_a1 && hash_b2 == hash_a2) {
++cnt_ap;
if (cnt_ap <= MAX_AP)
ap[cnt_ap] = i - (int)a.size();
}
}
out << cnt_ap << '\n';
for (int i = 1; i <= std::min(cnt_ap, MAX_AP); ++i)
out << ap[i] << ' ';
return 0;
}