Pagini recente » Cod sursa (job #3264627) | Cod sursa (job #2757891) | Cod sursa (job #1142480) | Cod sursa (job #1103877) | Cod sursa (job #2297326)
#include <bits/stdc++.h>
#define MOD1 104053
#define MOD2 104059
#define P 31
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
string a, b;
int h1[2000100], h2[2000100], lena, lenb, rs, pw1[2000100], pw2[2000100], hash1, hash2, hsh1, hsh2;
vector <int> sol;
int main() {
in >> a >> b;
lena = a.size();
lenb = b.size();
pw1[0] = 1;
pw2[0] = 1;
for (int i = 1; i <= lenb + 1; i++) {
pw1[i] = (pw1[i - 1] * P) % MOD1;
pw2[i] = (pw2[i - 1] * P) % MOD2;
}
for (int i = 0; i < lena; i++) {
hash1 = (hash1 + (int) a[i] * pw1[lena - i - 1]) % MOD1;
hash2 = (hash2 + (int) a[i] * pw2[lena - i - 1]) % MOD2;
hsh1 = (hsh1 + (int) b[i] * pw1[lena - i - 1]) % MOD1;
hsh2 = (hsh2 + (int) b[i] * pw2[lena - i - 1]) % MOD2;
}
if (hsh1 == hash1 && hsh2 == hash2)
sol.push_back(0);
for (int i = lena; i < lenb; i++) {
hsh1 = (P * hsh1 - pw1[lena] * (int) b[i - lena] + b[i]) % MOD1;
hsh2 = (P * hsh2 - pw2[lena] * (int) b[i - lena] + b[i]) % MOD2;
hsh1 = (hsh1 + MOD1) % MOD1;
hsh2 = (hsh2 + MOD2) % MOD2;
if (hsh1 == hash1 && hsh2 == hash2)
sol.push_back(i - lena + 1);
}
out << sol.size() << '\n';
int cnt = 1;
for (auto i : sol)
if (cnt <= 1000) {
cnt++;
out << i << ' ';
}
return 0;
}