Pagini recente » Cod sursa (job #3292739) | Cod sursa (job #3259443) | Cod sursa (job #2355522) | Cod sursa (job #1642841) | Cod sursa (job #3298323)
#include <bits/stdc++.h>
using namespace std;
int base = 512;
int MOD = 1000000007;
int rollingHash[2000005];
int bases[2000005];
int generateHash(string s) {
// hash(s) = s[0] + s[1] * b + s[2] * b ^ 2 + ...
int hash = 0;
for (int i = (int) s.size() - 1; i >= 0; i--) {
hash = (1LL * hash * base + s[i]) % MOD;
}
return hash;
}
void rollHash(string s) {
for (int i = (int) s.size() - 1; i >= 0; i--) {
rollingHash[i] = (1LL * rollingHash[i + 1] * base + s[i]) % MOD;
}
}
int getHashInterval(int left, int right) {
return ((rollingHash[left] - 1LL * rollingHash[right + 1] * bases[right - left + 1]) % MOD + MOD) % MOD;
}
void buildBases() {
bases[0] = 1;
for (int i = 1; i <= 2000000; ++i) {
bases[i] = (1LL * bases[i - 1] * base) % MOD;
}
}
int main()
{
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
string s, t;
cin >> s >> t;
buildBases();
int hash = generateHash(s);
rollHash(t);
int counter = 0;
for (int i = 0; i + s.size() <= t.size(); ++i) {
if (hash == getHashInterval(i, i + s.size() - 1)) {
counter++;
}
}
cout << counter << '\n';
counter = 0;
for (int i = 0; i + s.size() <= t.size() and counter < 1000; ++i) {
if (hash == getHashInterval(i, i + s.size() - 1)) {
counter++;
cout << i << ' ';
}
}
return 0;
}