Pagini recente » Cod sursa (job #1878913) | Cod sursa (job #2963444) | Cod sursa (job #2986605) | Cod sursa (job #1194177) | Cod sursa (job #2243694)
#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> ans;
const int base = 73, mod1 = 666013, mod2 = 1000000007;
string word, text;
int rid(int baza, int exp, int mod){
int rez = 1;
while(exp > 0){
if(exp % 2){
rez = (1LL * rez * baza) % mod;
}
baza = (1LL * baza * baza) % mod;
exp /= 2;
}
return rez;
}
void RabinKarp(string pat, string txt){
int pathash1 = 0, pathash2 = 0, txthash1 = 0, txthash2 = 0;
for(int i = 0; i < int(pat.size()); ++i){
pathash1 = (1LL * base * pathash1 + int(pat[i])) % mod1;
pathash2 = (1LL * base * pathash2 + int(pat[i])) % mod2;
txthash1 = (1LL * base * txthash1 + int(txt[i])) % mod1;
txthash2 = (1LL * base * txthash2 + int(txt[i])) % mod2;
}
int pow1 = rid(base, int(pat.size()) - 1, mod1), pow2 = rid(base, int(pat.size()) - 1, mod2);
if(pathash1 == txthash1 && pathash2 == txthash2)
ans.push_back(0);
for(int i = int(pat.size()); i < int(txt.size()); ++i){
txthash1 = (1LL * (txthash1 - (int(txt[i - int(pat.size())]) * pow1) % mod1 + mod1) * base + int(txt[i])) % mod1;
txthash2 = (1LL * (txthash2 - (int(txt[i - int(pat.size())]) * pow2) % mod2 + mod2) * base + int(txt[i])) % mod2;
if(pathash1 == txthash1 && pathash2 == txthash2)
ans.push_back(i - int(pat.size()) + 1);
}
}
int main()
{
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
fin >> word >> text;
RabinKarp(word, text);
int len = min(1000, int(ans.size()));
fout << ans.size() << "\n";
for(int i = 0; i < len; ++i)
fout << ans[i] << " ";
return 0;
}