Pagini recente » Cod sursa (job #1254504) | Cod sursa (job #2979745) | Cod sursa (job #1825268) | Cod sursa (job #862546) | Cod sursa (job #3171109)
#include <iostream>
#include <vector>
#include <string>
const int MOD1 = 666013;
const int BASE1 = 101;
const int BASE2 = 103;
const int MOD2 = 666019;
int cnt;
std::vector<int> rez;
void HashFunc(const std::string& pattern, const std::string& str) {
int M = pattern.size();
int N = str.size();
int pattern_hash1 = 0;
int pattern_hash2 = 0;
int str_hash1 = 0;
int str_hash2 = 0;
int power = 1;
for (int i = 0; i < M - 1; i++)
power = (power * BASE1) % MOD1;
for (int i = 0, j = 0; i < M; i++) {
pattern_hash1 = (BASE1 * pattern_hash1 + pattern[i]) % MOD1;
pattern_hash2 = (BASE2 * pattern_hash2 + pattern[i]) % MOD2;
str_hash1 = (BASE1 * str_hash1 + str[i]) % MOD1;
str_hash2 = (BASE2 * str_hash2 + str[i]) % MOD2;
}
for (int i = 0, j = 0; i <= N - M; ++i) {
if (pattern_hash1 == str_hash1 && pattern_hash2 == str_hash2) {
if (j == M) {
if (rez.size() < 1000) {
rez.push_back(i);
}
cnt++;
}
}
if (i < N - M) {
str_hash1 = (BASE1 * (str_hash1 - str[i] * power) + str[i + M]) % MOD1;
str_hash2 = (BASE2 * (str_hash2 - str[i] * power) + str[i + M]) % MOD2;
if (str_hash1 < 0)
str_hash1 += MOD1;
if (str_hash2 < 0)
str_hash2 += MOD2;
}
j++;
}
}
int main() {
std::string pattern, str;
std::cin >> pattern >> str;
HashFunc(pattern, str);
std::cout << cnt << '\n';
for (int i = 0; i < rez.size(); i++) {
std::cout << rez[i] << ' ';
}
return 0;
}