Pagini recente » Cod sursa (job #1583196) | Cod sursa (job #1754137) | Cod sursa (job #576025) | Cod sursa (job #2867631) | Cod sursa (job #2763564)
#include <bits/stdc++.h>
using namespace std;
const int N = 2e6 + 10;
int MOD[2] = {1000000007, 1000000033};
int P[2] = {57, 61};
int pw[2][N], inv[2][N];
long long power(long long base, long long exp, int MOD) {
long long ans = 1;
while (exp > 0) {
if (exp % 2 == 1) {
ans = (ans * base) % MOD;
}
base = (base * base) % MOD;
exp >>= 1;
}
return ans;
}
void build(int lim) {
for (int i = 0; i < 2; i++) {
pw[i][0] = 1;
inv[i][0] = 1;
}
int aux[2] = {power(P[0], MOD[0] - 2, MOD[0]), power(P[1], MOD[1] - 2, MOD[1])};
for (int i = 0; i < 2; i++) {
for (int j = 1; j < lim; j++) {
pw[i][j] = (1ll * pw[i][j - 1] * P[i]) % MOD[i];
inv[i][j] = (1ll * inv[i][j - 1] * aux[i]) % MOD[i];
}
}
}
vector<int> buildHash(string &s, int id) {
int n = s.size();
vector<int> sum(n, 0);
for (int i = 0; i < n; i++) {
if (i > 0) {
sum[i] = sum[i - 1];
}
sum[i] += (1ll * pw[id][i] * s[i]) % MOD[id];
sum[i] %= MOD[id];
}
return sum;
}
int getHash(vector<int> &sum, int id, int l, int r) {
int ans = sum[r] - (l > 0 ? sum[l - 1] : 0);
ans = (ans % MOD[id] + MOD[id]) % MOD[id];
ans = (1ll *ans * inv[id][l]) % MOD[id];
return ans;
}
int main() {
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
string a[2];
cin >> a[0] >> a[1];
build(max(a[0].size(), a[1].size()));
vector<int> hashes[2][2];
for (int i = 0; i < 2; i++) {
for (int j = 0; j < 2; j++) {
hashes[i][j] = buildHash(a[i], j);
}
}
vector<int> id;
int l = a[0].size();
for (int i = 0; i + l - 1 < a[1].size(); i++) {
int f = 1;
for (int j = 0; j < 2; j++) {
if (getHash(hashes[0][j], j, 0, l - 1) != getHash(hashes[1][j], j, i, i + l - 1)) {
f = 0;
break;
}
}
if (f) {
id.push_back(i);
}
}
cout << id.size() << '\n';
for (int i = 0; i < min(1000, (int) id.size()); i++) {
cout << id[i] << ' ';
}
return 0;
}