Pagini recente » Cod sursa (job #2861878) | Cod sursa (job #3124580) | Cod sursa (job #429974) | Cod sursa (job #843497) | Cod sursa (job #1258950)
#include <cstdint>
#include <fstream>
#include <string>
#include <vector>
using namespace std;
constexpr uint64_t M1 = 15485863;
constexpr uint64_t M2 = 15485867;
constexpr uint64_t B = 128;
inline uint64_t hashf(const string& text, const uint64_t base, const uint64_t m);
struct StringHash{
uint64_t base;
uint64_t rehash_base;
uint64_t m;
StringHash(uint64_t base, uint64_t rehash_base, uint64_t m) : base(base), rehash_base(rehash_base), m(m) {}
uint64_t operator()(const string& text) const {
uint64_t result = 0;
for (char c : text)
result = ((result * base) % m + c) % m;
return result;
}
uint64_t rehash(uint64_t old_h, char c_significant, char c_new) const {
return ((old_h * base) % m + m - (c_significant * rehash_base) % m + c_new) % m;
}
};
inline uint64_t pow_mod(uint64_t base, uint64_t exp, uint64_t mod) {
uint64_t result = 1;
while (exp) {
if (exp % 2)
result = (result * base) % mod;
base = (base * base) % mod;
exp /= 2;
}
return result;
}
int main() {
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string query, text;
fin >> query >> text;
if (query.size() > text.size()) {
fout << "0\n";
return 0;
}
uint64_t B1 = pow_mod(B, query.size(), M1),
B2 = pow_mod(B, query.size(), M2);
StringHash hash1(B, B1, M1), hash2(B, B2, M2);
size_t matches = 0;
size_t positions[1001];
uint64_t HQ1 = hash1(query);
uint64_t HQ2 = hash2(query);
size_t i = 0;
uint64_t h1 = hash1(text.substr(0, query.size())),
h2 = hash2(text.substr(0, query.size()));
while (true) {
if (h1 == HQ1 && h2 == HQ2) {
matches++;
if (matches <= 1000) positions[matches] = i;
}
if (i + query.size() < text.size()) {
h1 = hash1.rehash(h1, text[i], text[i + query.size()]);
h2 = hash2.rehash(h2, text[i], text[i + query.size()]);
i++;
}
else break;
}
fout << matches << '\n';
for (size_t i = 1; i <= 1000 && i <= matches; ++i) fout << positions[i] << ' ';
fout << endl;
return 0;
}