Pagini recente » Cod sursa (job #1802746) | Cod sursa (job #19967) | Cod sursa (job #1948731) | Cod sursa (job #1904779) | Cod sursa (job #2243691)
#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<long long> ans;
const long long base = 73, mod1 = 666013, mod2 = 1000000007;
string word, text;
long long rid(long long baza, long long exp, long long mod){
long long rez = 1;
while(exp > 0){
if(exp % 2){
rez *= baza;
rez %= mod;
}
baza *= baza;
baza %= mod;
exp /= 2;
}
return rez;
}
void RabinKarp(string pat, string txt){
long long pathash1 = 0, pathash2 = 0, txthash1 = 0, txthash2 = 0;
for(long long i = 0; i < int(pat.size()); ++i){
pathash1 = (base * pathash1 + int(pat[i])) % mod1;
pathash2 = (base * pathash2 + int(pat[i])) % mod2;
txthash1 = (base * txthash1 + int(txt[i])) % mod1;
txthash2 = (base * txthash2 + int(txt[i])) % mod2;
}
long long 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(long long i = int(pat.size()); i < int(txt.size()); ++i){
txthash1 = ((txthash1 - (int(txt[i - int(pat.size())]) * pow1) % mod1 + mod1) * base + int(txt[i])) % mod1;
txthash2 = ((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);
long long len = min(1000, int(ans.size()));
fout << ans.size() << "\n";
for(long long i = 0; i < len; ++i)
fout << ans[i] << " ";
return 0;
}