Pagini recente » Cod sursa (job #167253) | Cod sursa (job #1122251) | Cod sursa (job #1843866) | Cod sursa (job #954166) | Cod sursa (job #964617)
Cod sursa(job #964617)
//BEGIN CUT
#include <fstream>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
//END CUT
struct Rabin_Karp {
const int base = 73, modulo1 = 100007, modulo2 = 100021;
vector<int> get_matches(const string &text, const string &pattern) {
vector<int> matches;
int hp1, hp2, hs1, hs2;
int base_pow1 = 1, base_pow2 = 1;
hp1 = hp2 = pattern[0];
hs1 = hs2 = text[0];
for (int i = 1; i < pattern.size(); ++i)
{
base_pow1 = (base_pow1 * base) % modulo1;
base_pow2 = (base_pow2 * base) % modulo2;
hp1 = (hp1 * base + pattern[i]) % modulo1;
hs1 = (hs1 * base + text[i]) % modulo1;
hp2 = (hp2 * base + pattern[i]) % modulo2;
hs2 = (hs2 * base + text[i]) % modulo2;
}
if (hp1 == hs1 && hp2 == hs2)
matches.push_back(0);
for (int i = pattern.size(); i < text.size(); ++i)
{
hs1 = (base * ((hs1 - base_pow1 * text[i-pattern.size()]) % modulo1 + modulo1)
+ text[i]) % modulo1;
hs2 = (base * ((hs2 - base_pow2 * text[i-pattern.size()]) % modulo2 + modulo2)
+ text[i]) % modulo2;
if (hp1 == hs1 && hp2 == hs2)
matches.push_back(i - pattern.size() + 1);
}
return matches;
}
};
//BEGIN CUT
int main()
{
ifstream fin("strmatch.in");
ofstream fout ("strmatch.out");
string text, pattern;
fin >> pattern >> text;
/*
Rabin_Karp rp;
vector<int> matches = rp.get_matches(text, pattern);
fout << matches.size() << '\n';
for (auto &pos : matches)
fout << pos << ' ';
fout << '\n';
*/
const int base = 269, modulo1 = 611833, modulo2 = 611837;
int matches[1012], m=0;
int hp1, hp2, hs1, hs2;
int base_pow1 = 1, base_pow2 = 1;
hp1 = hp2 = pattern[0];
hs1 = hs2 = text[0];
for (int i = 1; i < pattern.size(); ++i)
{
base_pow1 = (base_pow1 * base) % modulo1;
base_pow2 = (base_pow2 * base) % modulo2;
hp1 = (hp1 * base + pattern[i]) % modulo1;
hs1 = (hs1 * base + text[i]) % modulo1;
hp2 = (hp2 * base + pattern[i]) % modulo2;
hs2 = (hs2 * base + text[i]) % modulo2;
}
if (hp1 == hs1 && hp2 == hs2)
matches[m++]=0;
for (int i = pattern.size(); i < text.size(); ++i)
{
hs1 = (base * ((hs1 - base_pow1 * text[i-pattern.size()]) % modulo1 + modulo1)
+ text[i]) % modulo1;
hs2 = (base * ((hs2 - base_pow2 * text[i-pattern.size()]) % modulo2 + modulo2)
+ text[i]) % modulo2;
if (hp1 == hs1 && hp2 == hs2)
{
if (m < 1000)
matches[m] = i - pattern.size() + 1;
m++;
}
}
fout << m << '\n';
for (int i = 0; i < m && i < 1000; ++i)
fout << matches[i] << ' ';
fout << endl;
fout.close();
return 0;
}
//END CUT