Pagini recente » Cod sursa (job #2649884) | Cod sursa (job #2756897) | Cod sursa (job #84183) | Cod sursa (job #2359962) | Cod sursa (job #2937487)
#include <bits/stdc++.h>
#define NMAX 2000010
#define ll long long
using namespace std;
const int MOD = 1e9 + 9, p = 31;
string A, B;
ll Hash[NMAX];
ll compute_hash(const string& s) {
ll val = 0, P = 1;
for (auto ch: s) {
val = (val + (ch - 'A' + 1) * P) % MOD;
P = (P * p) % MOD;
}
return val;
}
ll inv(ll x) {
ll P = x, b = MOD - 2, ans = 1;
while (b) {
if (b % 2)
ans = (1LL * ans * P) % MOD;
P = (1LL * P * P) % MOD;
b /= 2;
}
return ans;
}
int main() {
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
ios_base::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
cin >> A >> B;
if (A.size() > B.size()) {
cout << 0;
return 0;
}
ll hashA = compute_hash(A);
string crt;
for (int i = 0; i < B.size(); i++) {
crt += B[i];
Hash[i + 1] = compute_hash(crt);
}
ll aux = compute_hash("CAB");
vector<int> ans;
ll P = 1, M = B.size() - A.size() + 1;
for (int i = 0; i < M; i++) {
ll crtHash = (Hash[i + A.size()] - Hash[i] + MOD) % MOD;
crtHash = (crtHash * inv(P)) % MOD;
P = (P * p) % MOD;
if (crtHash == hashA)
ans.push_back(i);
}
cout << ans.size() << '\n';
for (int i = 0; i < min((int)ans.size(), 1000); i++)
cout << ans[i] << ' ';
}