Pagini recente » Cod sursa (job #1475911) | Cod sursa (job #2869348) | Cod sursa (job #1936390) | Cod sursa (job #22741) | Cod sursa (job #3295972)
#include <iostream>
#include <vector>
#define base 512
#define mod 1'000'000'007
#define int long long
using namespace std;
signed h[2'000'005];
signed 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] = 1ll * (h[i] * base % mod + s[i]) % mod;
pow[i] = 1ll * pow[i - 1] * base % mod;
}
int hsh = 0;
for(int i = 0; i < a.size(); i ++) {
hsh = 1ll * 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);
}
}
cout << ans.size() << '\n';
int cnt = 0;
for(auto i : ans) {
cout << i << ' ';
cnt ++;
if(cnt == 1000)
break;
}
// cout << '\n' << query(7, 9) << ' ' << hsh;
}