Pagini recente » Cod sursa (job #420222) | Cod sursa (job #1441011) | Cod sursa (job #1393865) | Cod sursa (job #1613654) | Cod sursa (job #2763559)
#include <bits/stdc++.h>
using namespace std;
long long power(long long base, long long exp, int MOD) {
long long ans = 1;
while (exp > 0) {
if (exp % 2 == 1) {
ans = (ans * base) % MOD;
}
base = (base * base) % MOD;
exp >>= 1;
}
return ans;
}
vector<long long> buildHash(string &s, int P, int MOD) {
int n = s.size();
vector<long long> sum(n, 0);
for (int i = 0; i < n; i++) {
if (i > 0) {
sum[i] = sum[i - 1];
}
sum[i] += (power(P, i, MOD) * s[i]) % MOD;
sum[i] %= MOD;
}
return sum;
}
long long getHash(vector<long long> &sum, int P, int MOD, int l, int r) {
long long ans = sum[r] - (l > 0 ? sum[l - 1] : 0);
ans = (ans % MOD + MOD) % MOD;
ans = (ans * power(power(P, l, MOD), MOD - 2, MOD)) % MOD;
return ans;
}
int main() {
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
string a[2];
cin >> a[0] >> a[1];
int MOD[2] = {1000000007, 1000000033};
int P[2] = {57, 61};
vector<int> id;
vector<long long> hashes[2][2];
for (int i = 0; i < 2; i++) {
for (int j = 0; j < 2; j++) {
hashes[i][j] = buildHash(a[i], P[j], MOD[j]);
}
}
int l = a[0].size();
for (int i = 0; i + l - 1 < a[1].size(); i++) {
int f = 1;
for (int j = 0; j < 2; j++) {
if (getHash(hashes[0][j], P[j], MOD[j], 0, l - 1) != getHash(hashes[1][j], P[j], MOD[j], i, i + l - 1)) {
f = 0;
break;
}
}
if (f) {
id.push_back(i);
}
}
cout << id.size() << '\n';
for (int i = 0; i < min(1000, (int) id.size()); i++) {
cout << id[i] << ' ';
}
return 0;
}