Pagini recente » Cod sursa (job #2406127) | Cod sursa (job #2803493) | Cod sursa (job #75336) | Cod sursa (job #1547987) | Cod sursa (job #2814181)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
#define int long long
const int p = 37;
const int mod1 = 1e9 + 9;
const int mod2 = 1e9 + 7;
vector <int> ans;
signed main() {
string s; fin >> s;
string t; fin >> t;
int pow1 = 1, pow2 = 1;
int H1 = 0, H2 = 0, h1 = 0, h2 = 0;
for(int i = 0; i < s.size(); ++i) {
H1 = (1ll * H1 * p + s[i]) % mod1;
H2 = (1ll * H2 * p + s[i]) % mod2;
h1 = (1ll * h1 * p + t[i]) % mod1;
h2 = (1ll * h2 * p + t[i]) % mod2;
if(i > 0) pow1 = (1ll * pow1 * p) % mod1;
if(i > 0) pow2 = (1ll * pow2 * p) % mod2;
}
if(h1 == H1 && h2 == H2) {
ans.push_back((int)s.size() - 1);
}
for(int i = s.size(); i < t.size(); ++i) {
h1 = ((1ll * h1 - (1LL * pow1 * t[i-s.size()] % mod1) + mod1) % mod1 * p + t[i]) % mod1;
h2 = ((1ll * h2 - (1LL * pow2 * t[i-s.size()] % mod2) + mod2) % mod2 * p + t[i]) % mod2;
if(h1 == H1 && h2 == H2) {
ans.push_back(i);
}
}
fout << ans.size() << '\n';
for(int i = 0; i < min((int)1000, (int)ans.size()); ++i)
fout << i - s.size() + 1 << " ";
return 0;
}