Pagini recente » Cod sursa (job #1617389) | Cod sursa (job #756415) | Cod sursa (job #1752980) | Cod sursa (job #712485) | Cod sursa (job #2238795)
#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> ans;
const int base = 256, mod = 101;
string word, text;
int rid(int baza, int exp){
int 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){
int pathash = 0, txthash = 0;
for(int i = 0; i < int(pat.size()); ++i){
pathash = (pathash * base + int(pat[i])) % mod;
txthash = (txthash * base + int(txt[i])) % mod;
}
int pow = rid(base, int(pat.size()) - 1);
for(int i = 0; i < int(txt.size()) - int(pat.size()); ++i){
if(pathash == txthash){
int ok = 1;
for(int j = 0; j < int(pat.size()) && ok; ++j){
if(pat[j] != txt[i + j])
ok = 0;
}
if(ok)
ans.push_back(i);
}
if(i < int(txt.size()) - int(pat.size())){
txthash = (base * (txthash - pow * int(txt[i])) + int(txt[i + int(pat.size())])) % mod;
if(txthash < 0)
txthash += mod;
}
}
}
int main()
{
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
fin >> word >> text;
RabinKarp(word, text);
int len = min(1000, int(ans.size()));
fout << len << "\n";
for(int i = 0; i < len; ++i)
fout << ans[i] << " ";
return 0;
}