Pagini recente » Cod sursa (job #1371961) | Cod sursa (job #1122995) | Cod sursa (job #3221395) | Cod sursa (job #1870635) | Cod sursa (job #2747607)
#include <iostream>
#include <fstream>
#include <string>
#include <algorithm>
const int MOD = 666013;
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_a = 0;
for (char i : a)
hash_a = (hash_a * BASE + (i - 'A')) % MOD;
int hash_b = 0;
for (int i = 0; i < a.size(); ++i)
hash_b = (hash_b * BASE + (b[i] - 'A')) % MOD;
int power = 1;
for (int i = 1; i < a.size(); ++i)
power = (power * BASE) % MOD;
for (int i = (int)a.size(); i < b.size(); ++i) {
hash_b = ((hash_b - power * (b[i - (int)a.size()] - 'A') + MOD) * BASE + (b[i] - 'A')) % MOD;
if (hash_b == hash_a) {
++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;
}