Pagini recente » Cod sursa (job #2281210) | Cod sursa (job #332710) | Cod sursa (job #2711999) | Cod sursa (job #3005475) | Cod sursa (job #3138816)
#include <iostream>
#include <fstream>
#include <vector>
const int P = 67;
const int M1 = 1e9 + 9;
const int M2 = 1e9 + 7;
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<unsigned int> pow_M1(std::max(s.size(), t.size()));
std::vector<unsigned int> pow_M2(std::max(s.size(), t.size()));
pow_M1[0] = 1;
pow_M2[0] = 1;
for (int i = 1; i < pow_M1.size(); ++i) {
pow_M1[i] = pow_M1[i - 1] * P % M1;
pow_M2[i] = pow_M2[i - 1] * P % M2;
}
std::vector<unsigned int> hash_sum_M1(t.size() + 1, 0);
std::vector<unsigned int> hash_sum_M2(t.size() + 1, 0);
int size = (int) t.size();
for (int i = 0; i < size; ++i) {
hash_sum_M1[i + 1] = (hash_sum_M1[i] + get_code(t[i]) * pow_M1[i]) % M1;
hash_sum_M2[i + 1] = (hash_sum_M2[i] + get_code(t[i]) * pow_M2[i]) % M2;
}
long long search_hash_M1 = 0;
long long search_hash_M2 = 0;
for (int i = 0; i < s.size(); ++i) {
search_hash_M1 = (search_hash_M1 + get_code(s[i]) * pow_M1[i]) % M1;
search_hash_M2 = (search_hash_M2 + get_code(s[i]) * pow_M2[i]) % M2;
}
std::vector<int> pos;
for (int i = 0; i - 1 + s.size() < size; ++i) {
long long current_hash_M1 = (hash_sum_M1[i + s.size()] + M1 - hash_sum_M1[i]) % M1;
long long current_hash_M2 = (hash_sum_M2[i + s.size()] + M2 - hash_sum_M2[i]) % M2;
if (search_hash_M1 * pow_M1[i] % M1 == current_hash_M1 &&
search_hash_M2 * pow_M2[i] % M2 == current_hash_M2) {
pos.push_back(i);
}
}
output << pos.size() << '\n';
for (const auto &x: pos) output << x << " ";
return 0;
}