Pagini recente » Cod sursa (job #137722) | Cod sursa (job #156247) | Cod sursa (job #3040207) | Cod sursa (job #415213) | Cod sursa (job #3138814)
#include <iostream>
#include <fstream>
#include <vector>
const int P = 67;
const int M = 1e9 + 9;
long long get_code(char x) {
if ('0' <= x && x <= '9') return x - '0' + 53;
else if ('a' <= x && x <= 'z') return x - 'a' + 1;
else return x - 'A' + 27;
}
int main() {
std::ifstream input("strmatch.in");
std::ofstream output("strmatch.out");
std::string s, t;
input >> s >> t;
std::vector<long long> pow(std::max(s.size(), t.size()));
pow[0] = 1;
for (int i = 1; i < pow.size(); ++i) {
pow[i] = pow[i - 1] * P % M;
}
std::vector<long long> hash_sum(t.size() + 1, 0);
int size = (int) t.size();
for (int i = 0; i < size; ++i) {
hash_sum[i + 1] = (hash_sum[i] + get_code(t[i]) * pow[i]) % M;
}
long long search_hash = 0;
for (int i = 0; i < s.size(); ++i) {
search_hash = (search_hash + get_code(s[i]) * pow[i]) % M;
}
std::vector<int> pos;
for (int i = 0; i - 1 + s.size() < size; ++i) {
long long current_hash = (hash_sum[i + s.size()] + M - hash_sum[i]) % M;
if (search_hash * pow[i] % M == current_hash) pos.push_back(i);
}
output << pos.size() << '\n';
for (const auto &x: pos) output << x << " ";
return 0;
}