test/aoj/ALDS1_14_B/main.test.cpp
Depends on
Code
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_14_B"
#include <iostream>
#include <string>
#include "Mylib/String/rolling_hash.cpp"
namespace hl = haar_lib;
int main() {
auto rh = hl::make_rh(1000000, 1000000007);
std::string t, p;
std::cin >> t >> p;
auto res = rh.find(t, p);
for (auto i : res) std::cout << i << "\n";
return 0;
}
#line 1 "test/aoj/ALDS1_14_B/main.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_14_B"
#include <iostream>
#include <string>
#line 2 "Mylib/String/rolling_hash.cpp"
#include <random>
#include <vector>
namespace haar_lib {
class rolling_hash {
std::vector<int64_t> pow_;
int64_t MOD_, BASE_;
public:
rolling_hash() {}
rolling_hash(int size, int MOD, int BASE) : MOD_(MOD), BASE_(BASE) {
pow_.assign(size + 1, 1);
for (int i = 1; i <= size; ++i) pow_[i] = pow_[i - 1] * BASE_ % MOD_;
}
template <typename T>
auto gen_hash_table(const T &s) const {
std::vector<int64_t> ret(s.size() + 1);
for (int i = 0; i < (int) s.size(); ++i) ret[i + 1] = (ret[i] * BASE_ + s[i]) % MOD_;
return ret;
}
template <typename T>
auto gen_hash(const T &s) const {
int64_t ret = 0;
for (int i = 0; i < (int) s.size(); ++i) ret = (ret * BASE_ + s[i]) % MOD_;
return ret;
}
/**
* @attention [l, r)
*/
int64_t get(const std::vector<int64_t> &table, int l, int r) const {
return (table[r] - table[l] * pow_[r - l] % MOD_ + MOD_ * MOD_) % MOD_;
}
template <typename T>
std::vector<int> find(const T &s, const T &pattern) const {
auto hp = gen_hash(pattern);
auto hs = gen_hash_table(s);
std::vector<int> ret;
for (int i = 0; i <= ((int) s.size() - (int) pattern.size()); ++i) {
if (hp == get(hs, i, i + pattern.size())) ret.push_back(i);
}
return ret;
}
};
auto make_rh(int size, int MOD, int seed = 0) {
std::mt19937 rnd(seed);
std::uniform_int_distribution<> dist(2, MOD - 2);
return rolling_hash(size, MOD, dist(rnd));
}
} // namespace haar_lib
#line 6 "test/aoj/ALDS1_14_B/main.test.cpp"
namespace hl = haar_lib;
int main() {
auto rh = hl::make_rh(1000000, 1000000007);
std::string t, p;
std::cin >> t >> p;
auto res = rh.find(t, p);
for (auto i : res) std::cout << i << "\n";
return 0;
}
Back to top page