Pagini recente » Cod sursa (job #781168) | Cod sursa (job #3194098) | Diferente pentru preoni-2007/runda-2/solutii intre reviziile 40 si 35 | Cod sursa (job #3288575) | Cod sursa (job #3295966)
#include <iostream>
#include <vector>
#define base 512
#define mod 1'000'000'007
#define int long long
using namespace std;
int h[2'000'005];
int pow[2'000'005];
vector<int> ans;
int query(int st, int dr) {
st ++;
dr ++;
return (h[dr] - h[st - 1] * pow[dr - st + 1] % mod + mod) % mod;
}
signed main() {
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
string a, s; cin >> a >> s;
h[1] = s[0];
pow[0] = 1;
for(int i = 1; i < s.size(); i ++) {
h[i + 1] = (h[i] * base % mod + s[i]) % mod;
pow[i] = pow[i - 1] * base % mod;
}
int hsh = 0;
for(int i = 0; i < a.size(); i ++) {
hsh = hsh * base % mod + a[i];
}
for(int st = 0, dr = a.size() - 1; dr < s.size(); st ++, dr ++) {
if(hsh == query(st, dr)) {
ans.push_back(st);
}
if(ans.size() == 1000)
break;
}
cout << ans.size() << '\n';
for(auto i : ans) {
cout << i << ' ';
}
// cout << '\n' << query(7, 9) << ' ' << hsh;
}