ローリングハッシュ (daylight/string/rolling_hash.hpp)

• View this file on GitHub
• Last update: 2024-12-26 20:32:55+09:00
• Include: #include "daylight/string/rolling_hash.hpp"

Depends on

• 基本テンプレート (daylight/base.hpp)

Verified with

• test/aoj/alds1/string_search.test.cpp
• Test for PR#1 (test/handmade/rolling_hash.test.cpp)
• test/yosupo/string/zalgorithm.test.cpp
• test/yukicoder/430.test.cpp
• test/yukicoder/599.test.cpp

Code

#include "daylight/base.hpp"
/// @brief ローリングハッシュ
struct RollingHash {
private:
	static const uint64_t mod = (1ull << 61ull) - 1;
	using uint128_t = __uint128_t;
	static inline uint64_t base = 0;
	static inline vector<uint64_t> pow;
	vector<uint64_t> hash;

	// 必要分のpow配列を追加で求める。
	inline void expand(int sz) {
		int pre_sz = SZ(pow);
		if(pre_sz < sz + 1) {
			for(int i = pre_sz - 1; i < sz; i++) {
				pow.push_back(mul(pow[i], base));
			}
		}
	}
	static inline uint64_t add(uint64_t a, uint64_t b) {
		if((a += b) >= mod) a -= mod;
		return a;
	}

	static inline uint64_t mul(uint64_t a, uint64_t b) {
		uint128_t c = (uint128_t) a * b;
		return add(c >> 61, c & mod);
	}

public:
	/// @brief 指定した文字列に対して,ハッシュを前計算する
	/// @param s ハッシュを取る文字列
	RollingHash(const string& s)
		: RollingHash(vector<char>(s.begin(), s.end())) {
	}

	/// @brief 指定した配列に対して,ハッシュを前計算する
	/// @param s ハッシュを取る配列
	template<typename T>
	RollingHash(const vector<T>& s) {
		if(base == 0) {
			mt19937_64 mt(chrono::steady_clock::now()
							  .time_since_epoch()
							  .count());
			uniform_int_distribution<uint64_t> rand(
				1e9, RollingHash::mod - 1);
			base = rand(mt);
		    pow.push_back(1);
		}
		expand(SZ(s) + 1);
		hash = vector<uint64_t>(SZ(s) + 1);
		REP(i, SZ(s)) {
			hash[i + 1] = add(mul(hash[i], base), s[i]);
		}
	}

	/// @brief build関数で計算されたhash値をもとにbegin文字目からlength文字のhash値を求める
	/// @param begin 文字列の初期位置(0-indexed)
	/// @param length 文字列の長さ
	/// @return hash値
	uint64_t query(int begin, int length) {
		assert(begin + length <= SZ(hash));
		assert(begin >= 0);
		if(length == 0) {
			return 0;
		}
		assert(length > 0);
		expand(length);
		auto ret = add(hash[begin + length],
					   mod - mul(hash[begin], pow[length]));
		return ret;
	}
};

Traceback (most recent call last):
  File "/home/runner/.local/lib/python3.10/site-packages/competitive_verifier/oj_resolve/resolver.py", line 181, in resolve
    bundled_code = language.bundle(path, basedir=basedir)
  File "/home/runner/.local/lib/python3.10/site-packages/competitive_verifier/oj/verify/languages/cplusplus.py", line 252, in bundle
    bundler.update(path)
  File "/home/runner/.local/lib/python3.10/site-packages/competitive_verifier/oj/verify/languages/cplusplus_bundle.py", line 482, in update
    self.update(
  File "/home/runner/.local/lib/python3.10/site-packages/competitive_verifier/oj/verify/languages/cplusplus_bundle.py", line 477, in update
    raise BundleErrorAt(
competitive_verifier.oj.verify.languages.cplusplus_bundle.BundleErrorAt: daylight/base.hpp: line 103: unable to process #include in #if / #ifdef / #ifndef other than include guards

Back to top page