Pagini recente » Cod sursa (job #2365886) | Cod sursa (job #2772609) | Cod sursa (job #2372401) | Cod sursa (job #844662) | Cod sursa (job #2736328)
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define debug(x) cerr << #x << " = " << x << "\n";
ifstream in("strmatch.in");
ofstream out("strmatch.out");
const int pw = 37;
const int mod1 = (int)1e9 + 9;
const int mod2 = (int)1e9 + 7;
const int max_n = (int)2e6 + 5;
char s[max_n], p[max_n];
vector<int> ans;
int32_t main() {
in >> (p + 1) >> (s + 1);
int p1 = 1, p2 = 1;
int a1 = 0, a2 = 0, b1 = 0, b2 = 0;
int n = (int)strlen(p + 1);
int m = (int)strlen(s + 1);
for (int i = 1; i <= n; i++) {
a1 = (1LL * a1 * pw + p[i]) % mod1;
a2 = (1LL * a2 * pw + p[i]) % mod2;
b1 = (1LL * b1 * pw + s[i]) % mod1;
b2 = (1LL * b2 * pw + s[i]) % mod2;
if (i > 1) {
p1 = (1LL * p1 * pw) % mod1;
p2 = (1LL * p2 * pw) % mod2;
}
}
if (a1 == b1 && a2 == b2) {
ans.push_back(0);
}
for (int i = n + 1; i <= m; i++) {
b1 = (((1LL * b1 - (p1 * s[i - n] % mod1) + mod1)) % mod1 * pw + s[i]) % mod1;
b2 = (((1LL * b2 - (p2 * s[i - n] % mod2) + mod2)) % mod2 * pw + s[i]) % mod2;
if (a1 == b1 && a2 == b2) {
ans.push_back(i - n);
}
}
out << (int)ans.size() << "\n";
for (int i = 0; i < min((int)1000, (int)ans.size()); i++) {
out << ans[i] << " ";
}
return 0;
}