Pagini recente » Cod sursa (job #1979300) | Cod sursa (job #160612) | Cod sursa (job #416552) | Cod sursa (job #725081) | Cod sursa (job #3038913)
#include <iostream>
#include <fstream>
#include <vector>
#define BASE 256
#define MOD 101
int main() {
std::ifstream input("strmatch.in");
std::ofstream output("strmatch.out");
std::string a, b;
input >> a >> b;
std::vector<int> ans;
long long sum_check = 0;
long long window = 0;
int prod = 1;
for (int i = 0; i < a.size(); ++i) {
sum_check = (sum_check * BASE % MOD + a[i]) % MOD;
window = (window * BASE % MOD + b[i]) % MOD;
if (i > 0) prod = prod * BASE % MOD;
}
if (sum_check == window) ans.push_back(0);
for (int i = 1; i + a.size() - 1 < b.size(); ++i) {
window = ((window - b[i - 1] * prod) * BASE + b[i + a.size() - 1]) % MOD;
if (window < 0) window += MOD;
if (sum_check == window) {
bool match = true;
for (int j = 0; j < a.length() && match; ++j) {
if (a[j] != b[i + j]) match = false;
}
if (match) ans.push_back(i);
}
}
output << ans.size() << '\n';
for (auto &x: ans) output << x << " ";
return 0;
}