Pagini recente » Cod sursa (job #2897182) | Cod sursa (job #3213180) | Cod sursa (job #1364036) | Cod sursa (job #3215142) | Cod sursa (job #2813018)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
const long long p = 37;
const long long mod1 = 1e9 + 9;
const long long mod2 = 1e9 + 7;
vector <int> ans;
int main() {
string s; fin >> s;
string t; fin >> t;
if(s.size() > t.size()) { fout << '0'; return 0;}
long long Hash1 = 0, Hash2 = 0, pow1 = 1, pow2 = 1;
long long subH1 = 0, subH2 = 0;
for(int i = 0; i < s.size(); ++i) {
Hash1 = (1ll * Hash1 * p + s[i]) % mod1;
Hash2 = (1ll * Hash2 * p + s[i]) % mod2;
subH1 = (1ll * subH1 * p + t[i]) % mod1;
subH2 = (1ll * subH2 * p + t[i]) % mod2;
if(i != 0) pow1 = pow1 * p % mod1;
if(i != 0) pow2 = pow2 * p % mod2;
}
if(subH1 == Hash1 && subH2 == Hash2) {
ans.push_back(0);
}
for(int i = s.size(); i < t.size(); ++i) {
if(i + 1 <= s.size()) {
subH1 = (subH1 * p + t[i]) % mod1;
subH2 = (subH2 * p + t[i]) % mod2;
} else {
subH1 = (1ll * subH1 - (pow1 * t[i-s.size()]) % mod1 + mod1) % mod1;
subH2 = (1ll * subH2 - (pow2 * t[i-s.size()]) % mod2 + mod2) % mod2;
subH1 = (1ll * subH1 * p + t[i]) % mod1;
subH2 = (1ll * subH2 * p + t[i]) % mod2;
if(subH1 == Hash1 && subH2 == Hash2) {
if(ans.size() < 1000)
ans.push_back(i);
else i = t.size();
}
}
}
fout << ans.size() << '\n';
for(int i : ans)
fout << i - s.size() + 1 << " ";
return 0;
}