{"id":1549,"date":"2021-01-12T21:01:53","date_gmt":"2021-01-13T05:01:53","guid":{"rendered":"http:\/\/209.126.2.187\/?p=1549"},"modified":"2021-07-09T20:58:43","modified_gmt":"2021-07-10T03:58:43","slug":"rolling-hash-template","status":"publish","type":"post","link":"https:\/\/nanzhou.cc\/index.php\/2021\/01\/12\/rolling-hash-template\/","title":{"rendered":"Rolling Hash Template"},"content":{"rendered":"\n<h2 class=\"wp-block-heading\">With a Prime Modular<\/h2>\n\n\n\n<pre class=\"wp-block-code\"><code lang=\"cpp\" class=\"language-cpp line-numbers\">constexpr int kMaxN = 30'005;\nclass RollingHash {\npublic:\n  using ll = unsigned long long;\n  ll hashes[kMaxN];\n  ll base_to_i[kMaxN];\n  ll base_to_i_inverse[kMaxN];\n  \n  const int kBase;\n  const int kMod;\n  \n  RollingHash(string_view str, int kBase, int kMod) : kBase(kBase), kMod(kMod) {\n    int n = str.size();\n    ll curr_base = 1;\n    ll curr_sum = 0;\n    for (int i = 0; i &lt; n; ++i) {\n      curr_sum += (str[i] - 'a') * curr_base; \n      curr_sum %= kMod;\n      hashes[i] = curr_sum;\n      base_to_i[i] = curr_base;\n      curr_base = (curr_base * kBase) % kMod;\n    }\n    \n    base_to_i_inverse[n - 1] = GetInverse(base_to_i[n - 1]);\n    for (int i = n - 2; i &gt;= 0; --i) {\n      base_to_i_inverse[i] = (base_to_i_inverse[i + 1] * kBase) % kMod;\n    }\n  }\n  \n  \/\/ s[i, i + len - 1], s[j, j + len - 1]\n  bool Equal(int i, int j, int len, string_view str) {\n    int hash0 = (GetRelativeHash(i, i + len - 1) * base_to_i[j]) % kMod, hash1 = (GetRelativeHash(j, j + len - 1) * base_to_i[i]) % kMod;\n    \/\/ if (hash0 != hash1) {\n    \/\/     return false;\n    \/\/ } else {\n    \/\/     return str.substr(i, len) == str.substr(j, len);\n    \/\/ }\n    return hash0 == hash1;\n  }\n  \n  int GetHash(int left, int right) {\n    return (GetRelativeHash(left, right) * base_to_i_inverse[left]) % kMod;\n  }\n\nprivate:\n  \/\/ https:\/\/oi-wiki.org\/math\/fermat\/\n  \/\/ https:\/\/oi-wiki.org\/math\/inverse\/\n  ll GetInverse(int val) {\n    return FastPower(val, kMod - 2);\n  }\n  \n  ll FastPower(ll val, unsigned int n) {\n    if (n == 0) {\n      return 1;\n    }\n    if (n == 1) {\n      return val;\n    }\n    if (n % 2 == 0) {\n      return FastPower((val * val) % kMod, n \/ 2);\n    }\n    return (FastPower((val * val) % kMod, (n - 1) \/ 2) * val) % kMod;\n  }\n  \n  ll GetRelativeHash(int left, int right) {\n    return ((ll)hashes[right]  + kMod - ((left &gt;= 1) ? hashes[left - 1] : 0)) % kMod;\n  }\n};<\/code><\/pre>\n\n\n\n<h2 class=\"wp-block-heading\">2^64 as a Modular<\/h2>\n\n\n\n<pre class=\"wp-block-code\"><code lang=\"cpp\" class=\"language-cpp\">constexpr int kMaxN = 30'005;\nusing ll = uint64_t;\n\n\/\/ use 2^64 as kMod\nclass RollingHash {\npublic:\n  const int kBase;\n  \n  ll hashes[kMaxN];\n  ll base_to_i[kMaxN];\n\n  \/\/ hashes[i] = s[n - 1] * kBase^n-1-i + s[n - 2] * kBase^n-2-i + s[i] * kBase^0\n  RollingHash(string_view str, int kBase) : kBase(kBase) {\n    int n = str.size();\n    hashes[n] = 0;\n    for (int i = n - 1; i &gt;= 0; --i) {\n      hashes[i] = hashes[i + 1] * kBase + (str[i] - 'a');\n    }\n    \n    base_to_i[0] = 1;\n    for (int i = 1; i &lt; n; ++i) {\n      base_to_i[i] = base_to_i[i - 1] * kBase;\n    }\n  }\n  \n  \/\/ H(4) = s[4]\n  \/\/ H(3) = s[4] * kBase + s[3]\n  \/\/ H([3, 3]) = s[3]\n  ll GetHash(int left, int right) {\n    return hashes[left] - hashes[right + 1] * base_to_i[right - left + 1];\n  }\n};<\/code><\/pre>\n\n\n\n<h2 class=\"wp-block-heading\">Two Hash Functions<\/h2>\n\n\n\n<pre class=\"wp-block-code\"><code lang=\"cpp\" class=\"language-cpp\">struct PairHash {\n  size_t operator() (pair&lt;ll, ll> const&amp; p) const {\n    return p.first ^ p.second;\n  }\n};\nunordered_set&lt;pair&lt;ll, ll>, PairHash> visited;<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"<p>With a Prime Modular 2^64 as a Modular Two Hash Functions<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[67,54],"tags":[],"class_list":["post-1549","post","type-post","status-publish","format-standard","hentry","category-algorithm-template","category-string"],"_links":{"self":[{"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/posts\/1549","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/comments?post=1549"}],"version-history":[{"count":9,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/posts\/1549\/revisions"}],"predecessor-version":[{"id":1624,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/posts\/1549\/revisions\/1624"}],"wp:attachment":[{"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/media?parent=1549"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/categories?post=1549"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/tags?post=1549"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}