Pagini recente » Statistici Bora Vlad (BoraVlad) | Cod sursa (job #1963818) | Cod sursa (job #1892379) | Profil ΩMΣGΔ | Cod sursa (job #2581331)
#include <cstdio>
#include <iostream>
#include <vector>
using namespace std;
string pattern, text;
const int P = 73;
const int MOD = 1e9+9;
const int NMAX = 2000505;
long long P_POW[NMAX], H[NMAX];
int main() {
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
cin.tie(NULL);
ios_base::sync_with_stdio(false);
cin >> pattern >> text;
P_POW[0] = 1;
for (int exp = 1; exp < NMAX; exp++) {
P_POW[exp] = (P_POW[exp - 1] * P) % MOD;
}
int N = (int) pattern.size(), M = (int) text.size();
long long hash = 0L;
for (int idx = 0; idx < N; idx++) {
hash = (hash + P_POW[idx] * (pattern[idx] - 'A' + 1)) % MOD;
}
for (int idx = 0; idx < M; idx++) {
H[idx + 1] = (H[idx] + P_POW[idx] * (text[idx] - 'A' + 1)) % MOD;
}
int matches = 0;
vector<int> sol;
for (int st = 1; st <= M - N; st++) {
long long currH = (H[st + N - 1] + MOD - H[st - 1]) % MOD;
if ((hash * P_POW[st - 1]) % MOD == currH) {
matches++;
if (matches <= 1000) {
sol.push_back(st);
}
}
}
cout << matches << "\n";
for (auto match : sol) {
cout << match - 1 << " ";
}
cout << "\n";
return 0;
}