Pagini recente » Cod sursa (job #3363203) | Cod sursa (job #3363145) | Cod sursa (job #3363205) | Cod sursa (job #3363161) | Cod sursa (job #3363192)
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 9;
const int B = 67;
vector<int> h;
int lgpow(int a, int n) {
a %= MOD;
n %= MOD;
int p = 0;
for (; n; n >>= 1) {
if (n & 1)
p = p * a % MOD;
a = a * a % MOD;
}
return p;
}
int invMod(int a) {
return lgpow(a, MOD - 2);
}
int get(int i, int j) {
return int(1LL * ((h[j] - h[i-1]) % MOD) * invMod(lgpow(B, i - 1)));
}
signed main() {
#ifndef LOCAL
cin.tie(nullptr)->sync_with_stdio(false);
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
#endif
vector<int> mapare(128);
for (int i = 'a'; i < 'z'; ++i)
mapare[i] = i - 'a';
for (int i = 'A'; i < 'Z'; ++i)
mapare[i] = i - 'A' + 26;
for (int i = 0; i < 9; ++i)
mapare[i] = i + 52;
string a, b; cin >> a >> b;
int hashA = 0;
for (int i = 0; i < int(a.size()); ++i) {
hashA = int((hashA + 1LL * mapare[a[i]] * lgpow(B, i) % MOD) % MOD);
}
h.resize(b.size());
h[0] = int(1LL * mapare[b[0]] * invMod(B) % MOD);
for (int i = 1; i < int(h.size()); ++i) {
h[i] = int((h[i-1] + 1LL * mapare[b[i]] * lgpow(B, i - 1) % MOD) % MOD);
}
vector<int> ans;
for (int i = 0; i < int(b.size()); ++i) {
if (get(i, i + int(a.size()) - 1) == hashA)
ans.push_back(i + 1);
}
cout << ans.size() << '\n';
for (auto& i : ans) cout << i << ' ';
cout << '\n';
return 0;
}