Pagini recente » Cod sursa (job #2482995) | Cod sursa (job #2484961) | Cod sursa (job #1090747) | Cod sursa (job #288196) | Cod sursa (job #2973358)
#include <bits/stdc++.h>
using namespace std;
#ifndef LOCAL
ifstream in("strmatch.in");
ofstream out("strmatch.out");
#define cin in
#define cout out
#endif // LOCAL
const int NMAX = 2e6 + 8;
int b1 = 31, m1 = 1e9 + 7;
int b2 = 37, m2 = 1e9 + 9;
int pow1[NMAX], pow2[NMAX];
int pref1_y[NMAX], pref2_y[NMAX];
pair<int, int> substr(int st, int dr) {
// a - b % mod = (a + mod - b) % mod
// a - b * c % mod = (a + mod ^ 2 - b * c) % mod
int h1 = (1LL * pref1_y[dr] + 1LL * m1 * m1 - 1LL * pref1_y[st - 1] * pow1[dr - st + 1]) % m1;
int h2 = (1LL * pref2_y[dr] + 1LL * m2 * m2 - 1LL * pref2_y[st - 1] * pow2[dr - st + 1]) % m2;
return {h1, h2};
}
int main()
{
#ifndef LOCAL
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
#endif // LOCAL
pow1[0] = 1; pow2[0] = 1;
for(int i = 1; i < NMAX; i++) {pow1[i] = (1LL * pow1[i - 1] * b1) % m1;}
for(int i = 1; i < NMAX; i++) {pow2[i] = (1LL * pow2[i - 1] * b2) % m2;}
string x, y; cin >> x >> y;
int h1_x = 0, h2_x = 0;
for(auto ch : x) {
h1_x = (1LL * h1_x * b1 + 1LL * (ch - 'A' + 2)) % m1;
h2_x = (1LL * h2_x * b2 + 1LL * (ch - 'A' + 1)) % m2;
}
for(int i = 1; i <= y.size(); i++) {
char ch = y[i - 1];
pref1_y[i] = (1LL * pref1_y[i - 1] * b1 + (ch - 'A' + 2)) % m1;
pref2_y[i] = (1LL * pref2_y[i - 1] * b2 + (ch - 'A' + 1)) % m2;
}
vector<int> prt; int counter = 0;
for(int i = 1; i + x.size() - 1 <= y.size(); i++) {
pair<int, int> sub = substr(i, i + x.size() - 1);
if(sub == make_pair(h1_x, h2_x)) {
counter += 1;
if(prt.size() < 1000) {
prt.push_back(i - 1);
}
}
}
cout << counter << '\n';
for(auto e : prt) cout << e << " ";
return 0;
}