Pagini recente » Cod sursa (job #1111044) | Cod sursa (job #828757) | Cod sursa (job #2443384) | Cod sursa (job #794323) | Cod sursa (job #3352743)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
#define int long long
const int p = 131;
const int mod = 1000000007;
const int NMAX = 2000000;
int power[NMAX + 5];
int fast_pow(int a, int b) {
int ans = 1;
a %= mod;
while (b) {
if (b % 2) ans = (ans * a) % mod;
a = (a * a) % mod;
b /= 2;
}
return ans;
}
signed main() {
string a, b;
fin>>a>>b;
if (a.size() > b.size()) {
fout<<0<<"\n";
return 0;
}
power[0] = 1;
for (int i = 1; i <= b.size(); i++) {
power[i] = (power[i - 1] * p) % mod;
}
int inv_p = fast_pow(p, mod - 2);
int hash_verif = 0, hash_curr = 0;
for (int i = 0; i < (int)a.size(); i++) {
hash_verif = (hash_verif + power[i] * (int)a[i]) % mod;
hash_curr = (hash_curr + power[i] * (int)b[i]) % mod;
}
vector<int> pos;
if (hash_curr == hash_verif) {
pos.push_back(0);
}
for (int i = (int)a.size(); i < (int)b.size(); i++) {
int left = i - (int)a.size();
hash_curr = (hash_curr - (int)b[left] + mod) % mod;
hash_curr = (hash_curr * inv_p) % mod;
hash_curr = (hash_curr + power[(int)a.size() - 1] * (int)b[i]) % mod;
if (hash_curr == hash_verif) {
pos.push_back(left + 1);
}
}
fout<<pos.size()<<'\n';
int limit = min((int)pos.size(), 1000LL);
for (int i = 0; i < limit; i++) {
fout << pos[i]<<' ';
}
fout << '\n';
}