Pagini recente » Cod sursa (job #1142454) | Cod sursa (job #505665) | Cod sursa (job #666240) | Cod sursa (job #1490902) | Cod sursa (job #3231352)
#include <bits/stdc++.h>
using namespace std;
#define unsigned long long int
const int mod = 2000000011, p = 53, N = 2e6 + 5;
string a, b;
int hash1[N], hash2[N], n, m;
int pw(int a, int n) {
if (!n)
return 1;
else {
if (n % 2)
return a * pw(a, n - 1) % mod;
else {
int c = pw(a, n / 2);
return c * c % mod;
}
}
}
int cod(char c) {
if (islower(c)) {
return c - 'a' + 1;
} else {
return c - 'A' + 27;
}
}
int get_hash(int l, int r) {
return ((hash2[r] - hash2[l - 1] + mod) % mod) * pw(pw(p, l), mod - 2) % mod;
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> a >> b;
n = a.size(); m = b.size();
hash1[0] = cod(a[0]);
for (int i = 1; i < n; i++) {
hash1[i] = (cod(a[i]) * pw(p, i) % mod);
hash1[i] = (hash1[i - 1] + hash1[i]) % mod;
}
int hash_value_1 = hash1[n - 1];
hash2[0] = cod(b[0]);
for (int i = 1; i < m; i++) {
hash2[i] = (hash2[i - 1] + (cod(b[i])) * pw(p, i) % mod) % mod;
}
vector<int> ans;
int cnt = 0;
for (int i = 0; i < m - n + 1; i++) {
if (i > 0 && get_hash(i, i + n - 1) == hash_value_1) {
cnt++;
ans.emplace_back(i);
}
else if (i == 0 && hash2[n - 1] == hash_value_1) {
cnt++;
ans.emplace_back(i);
}
}
cout << cnt << '\n';
for (auto it : ans)
cout << it << ' ';
return 0;
}