algorithm
This documentation is automatically generated by online-judge-tools/verification-helper
test/aoj/ALDS1_14_B.test.cpp
- View this file on GitHub
- Last update: 2020-12-31 16:46:24+09:00
- Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_14_B
Depends on
Code
#define PROBLEM \
"http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_14_B"
#include <bits/stdc++.h>
using namespace std;
#define call_from_test
#include "../../cpp_src/string/RollingHash.hpp"
#undef call_from_test
using ll = long long;
using pii = pair<int, int>;
template <class T>
using V = vector<T>;
template <class T>
using VV = V<V<T>>;
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define rep(i, n) rep2(i, 0, n)
#define rep2(i, m, n) for (int i = m; i < (n); i++)
#define per(i, b) per2(i, 0, b)
#define per2(i, a, b) for (int i = int(b) - 1; i >= int(a); i--)
#define ALL(c) (c).begin(), (c).end()
#define SZ(x) ((int)(x).size())
constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n - 1); }
template <class T, class U>
void chmin(T& t, const U& u) {
if (t > u) t = u;
}
template <class T, class U>
void chmax(T& t, const U& u) {
if (t < u) t = u;
}
template <class T, class U>
ostream& operator<<(ostream& os, const pair<T, U>& p) {
os << "(" << p.first << "," << p.second << ")";
return os;
}
template <class T>
ostream& operator<<(ostream& os, const vector<T>& v) {
os << "{";
rep(i, v.size()) {
if (i) os << ",";
os << v[i];
}
os << "}";
return os;
}
#ifdef LOCAL
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
cerr << " " << H;
debug_out(T...);
}
#define debug(...) \
cerr << __LINE__ << " [" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#define dump(x) cerr << __LINE__ << " " << #x << " = " << (x) << endl
#else
#define debug(...) (void(0))
#define dump(x) (void(0))
#endif
int main() {
RollingHash rh;
string S, T;
cin >> S >> T;
auto vh = rh.build(S);
auto thash = rh.whole_hash(T);
int sl = SZ(S), tl = SZ(T);
for (int l = 0; l <= sl - tl; ++l) {
if (rh.query(vh, l, l + tl) == thash) {
cout << l << '\n';
}
}
return 0;
}#line 1 "test/aoj/ALDS1_14_B.test.cpp"
#define PROBLEM \
"http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_14_B"
#include <bits/stdc++.h>
using namespace std;
#define call_from_test
#line 1 "cpp_src/string/RollingHash.hpp"
class RollingHash {
public:
using u128 = __uint128_t;
using u64 = uint64_t;
static const u64 mod = (1ull << 61ull) - 1;
vector<u64> power;
const u64 base;
static inline u64 add(u64 a, u64 b) {
if ((a += b) >= mod) a -= mod;
return a;
}
static inline u64 mul(u64 a, u64 b) {
u128 c = (u128)a * b;
return add(c >> 61, c & mod);
}
// make sure that no different characters / elements have the same value
// modulo base
static inline u64 generate_base(int minB = 1000) {
mt19937_64 mt(chrono::steady_clock::now().time_since_epoch().count());
uniform_int_distribution<u64> rand(minB, RollingHash::mod - 1);
return rand(mt);
}
inline void expand(int sz) {
if (power.size() <= sz) {
int pre_sz = (int)power.size();
power.resize(sz + 1);
for (int i = pre_sz - 1; i < sz; i++) {
power[i + 1] = mul(power[i], base);
}
}
}
explicit RollingHash(u64 base = generate_base()) : base(base), power{1} {}
vector<u64> build(const string& s) const {
int sz = s.size();
vector<u64> vhash(sz + 1);
for (int i = 0; i < sz; i++) {
vhash[i + 1] = add(mul(vhash[i], base), s[i]);
}
return vhash;
}
template <class T>
vector<u64> build(const vector<T>& s) const {
int sz = s.size();
vector<u64> vhash(sz + 1);
for (int i = 0; i < sz; i++) {
vhash[i + 1] = add(mul(vhash[i], base), s[i]);
}
return vhash;
}
u64 query(const vector<u64>& s, int l, int r) {
expand(r - l);
return add(s[r], mod - mul(s[l], power[r - l]));
}
u64 merge(u64 h1, u64 h2, int h2len) {
expand(h2len);
return add(mul(h1, power[h2len]), h2);
}
u64 whole_hash(const string& s) const {
int sz = s.size();
u64 res = 0;
for (auto& c : s) res = add(mul(res, base), c);
return res;
}
};
#line 9 "test/aoj/ALDS1_14_B.test.cpp"
#undef call_from_test
using ll = long long;
using pii = pair<int, int>;
template <class T>
using V = vector<T>;
template <class T>
using VV = V<V<T>>;
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define rep(i, n) rep2(i, 0, n)
#define rep2(i, m, n) for (int i = m; i < (n); i++)
#define per(i, b) per2(i, 0, b)
#define per2(i, a, b) for (int i = int(b) - 1; i >= int(a); i--)
#define ALL(c) (c).begin(), (c).end()
#define SZ(x) ((int)(x).size())
constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n - 1); }
template <class T, class U>
void chmin(T& t, const U& u) {
if (t > u) t = u;
}
template <class T, class U>
void chmax(T& t, const U& u) {
if (t < u) t = u;
}
template <class T, class U>
ostream& operator<<(ostream& os, const pair<T, U>& p) {
os << "(" << p.first << "," << p.second << ")";
return os;
}
template <class T>
ostream& operator<<(ostream& os, const vector<T>& v) {
os << "{";
rep(i, v.size()) {
if (i) os << ",";
os << v[i];
}
os << "}";
return os;
}
#ifdef LOCAL
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
cerr << " " << H;
debug_out(T...);
}
#define debug(...) \
cerr << __LINE__ << " [" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#define dump(x) cerr << __LINE__ << " " << #x << " = " << (x) << endl
#else
#define debug(...) (void(0))
#define dump(x) (void(0))
#endif
int main() {
RollingHash rh;
string S, T;
cin >> S >> T;
auto vh = rh.build(S);
auto thash = rh.whole_hash(T);
int sl = SZ(S), tl = SZ(T);
for (int l = 0; l <= sl - tl; ++l) {
if (rh.query(vh, l, l + tl) == thash) {
cout << l << '\n';
}
}
return 0;
}