Pagini recente » Cod sursa (job #2362705) | Cod sursa (job #1398453) | Cod sursa (job #978505) | Cod sursa (job #2706803) | Cod sursa (job #2862523)
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
using ll = long long;
const string myf = "strmatch";
ifstream fin(myf + ".in");
ofstream fout(myf + ".out");
string a, b;
vector<int> poz;
inline int conv(char c) {
if (islower(c))
return c - 'a' + 1;
return c - 'A' + 26 + 1;
}
vector<int> rabin_karp(const string &pat, const string &t) {
const int p = 53; // larger than alphabet
const int mod = 1e9 + 9;
int patHash = 0;
int np = pat.size();
int nt = t.size();
vector<int> poz;
vector <long long> ppow(max(np, nt));
vector <long long> hashes(nt + 1, 0);
ppow[0] = 1;
for (int i = 1; i < (int)ppow.size(); ++i)
ppow[i] = (ppow[i - 1] * p) % mod;
for (int i = 0; i < nt; ++i)
hashes[i + 1] = (hashes[i] + conv(t[i]) * ppow[i]) % mod;
for (int i = 0; i < np; ++i)
patHash = (patHash + conv(pat[i]) * ppow[i]) % mod;
for (int i = 0; i + np - 1 < nt; ++i) {
ll cur_h = (hashes[i + np] + mod - hashes[i]) % mod;
if (cur_h == patHash * ppow[i] % mod)
poz.pb(i);
}
return poz;
}
int main() {
fin >> a >> b;
vector<int> poz;
poz = rabin_karp(a, b);
fout << poz.size() << '\n';
for (int i = 0; i < min((int)poz.size(), 1001); ++i)
fout << poz[i] << " ";
fin.close();
fout.close();
return 0;
}