{"id":1098,"date":"2020-04-30T22:19:02","date_gmt":"2020-05-01T05:19:02","guid":{"rendered":"http:\/\/209.126.2.187\/?p=1098"},"modified":"2024-02-03T19:18:18","modified_gmt":"2024-02-04T03:18:18","slug":"rolling-hash","status":"publish","type":"post","link":"https:\/\/nanzhou.cc\/index.php\/2020\/04\/30\/rolling-hash\/","title":{"rendered":"Rolling Hash"},"content":{"rendered":"\n

Summary<\/h2>\n\n\n\n

Rolling hash is a common technique to compare if two substrings are equal or not. Given O(n)<\/code> preprocessing time, the comparison becomes O(1)<\/code> at the best case. <\/p>\n\n\n\n

OJ<\/h2>\n\n\n\n\n\n\n\n\t\n\n\t
<\/td>Trick<\/th>Difficulty<\/th>\n<\/tr>\n<\/thead>\n
LC 1316. Distinct Echo Substrings<\/a><\/td>Rolling Hash + string_view or DP in Linear Structure + string_view<\/td>6 points<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n\n\n\n\n

Details<\/h2>\n\n\n\n

<\/p>\n\n\n\n

We use two large coprime numbers \"b\" for base and \"m\" for mod. We use a polynomial to calculate the hash value. Typical values are \"b=1e9+7\" and \"m=1e9+9\" <\/p>\n\n\n\n

  <\/span>   <\/span>\"\[f(s) = \sum s[i] \times b^i \pmod m\]\"<\/p><\/p>\n\n\n\n

Given a substring s[i, j]<\/code>, it is not difficult to get that the hash value of it is,<\/p>\n\n\n\n

  <\/span>   <\/span>\"\[f(s[i, j]) = \frac{(f(s[0, j]) - f(s[0, i - 1]) + m)}{b^i} \pmod m\]\"<\/p><\/p>\n\n\n\n

We could preprocess tables for all the \"f[0, i]\" and \"b^i\" in O(n)<\/code>. After that, the complexity of getting a hash value for any substring is O(1)<\/code>. <\/p>\n\n\n\n

We then have the following truth,<\/p>\n\n\n\n

  <\/span>   <\/span>\"\[f(str0)==f(str1) \centernot\implies str0==str1\ (hash\ collision)\]\"<\/p><\/p>\n\n\n\n

  <\/span>   <\/span>\"\[f(str0)\centernot=f(str1) \implies str0\centernot=sub1\]\"<\/p><\/p>\n\n\n\n

namespace {\n\nusing ll = unsigned long long;\nll kBase = 31;\nll kMod = 1000'000'007;\nconstexpr int kMax = 100'005;\n\n\/\/ sum(s[i] * kBase^i)\nll hashes[kMax];\n\/\/ kBase^i\nll base_to_i[kMax];\n\/\/ inverse(kBase^i)\nll base_to_i_inverse[kMax];\n\n}\n\nll FastPower(ll val, ll n);\n\n\/\/ we have\n\/\/  num * x = 1 \n\/\/  num ^ (kMod - 1) = 1\n\/\/ so x = num ^ (kMod - 2)\nll GetInverse(ll val) {\n  return FastPower(val, kMod - 2);\n}\n\nll FastPower(ll val, ll 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\nvoid Preprocess(string_view str) {\n  int n = str.size();\n  ll curr_base = 1;\n  ll curr_sum = 0;\n  for (int i = 0; i < 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 >= 0; --i) {\n    base_to_i_inverse[i] = (base_to_i_inverse[i + 1] * kBase) % kMod;\n  }\n}\n  \nll GetHash(int l, int r) {\n  return ((hashes[r] + kMod - (l - 1 >= 0 ? hashes[l - 1] : 0)) * base_to_i_inverse[l]) % kMod;\n}<\/code><\/pre>\n\n\n\n
Two Hash Functions<\/h3>\n\n\n\n
In LC 1044. Longest Duplicate Substring<\/a>, you might find out one hash rolling hash function causes collisions. Another technique for rolling hash is to use Two hash functions (two bases and two mods). <\/p>\n\n\n\n
   <\/span>   <\/span>\"\[f_i(s) = \sum s[i] \times b_i^i \pmod {m_i}\]\"<\/p><\/p>\n\n\n\n
   <\/span>   <\/span>\"\[f_1(s[i, j]) = \frac{(f_1(s[0, j]) - f_1(s[0, i - 1]) + m_1)}{b_1^i} \pmod {m_1}\]\"<\/p><\/p>\n\n\n\n
   <\/span>   <\/span>\"\[f_2(s[i, j]) = \frac{(f_2(s[0, j]) - f_2(s[0, i - 1]) + m_2)}{b_2^i} \pmod {m_2}\]\"<\/p><\/p>\n\n\n\n
Use f_1 ^ f_2<\/code> directly here will cause collisions. Instead, we use a hash set of pairs to store these two values. HashSet in the standard library helps us handle hash collisions, which is sufficient to pass the OJ.<\/p>\n\n\n\n
struct PairHash {\n    size_t operator() (pair<ll, ll> const &p) const {\n        return hash<int>()(p.first) ^ hash<int>()(p.second);\n    }\n};\n\nunordered_set<pair<int, int>, PairHash> visited;<\/code><\/pre>\n\n\n\n
Another technique you might use here is the Modular<\/strong> Multiplicative Inverse<\/strong>. Please refer to this post<\/a>.<\/p>\n\n\n\n
Rolling Hash Template <\/h2>\n\n\n\n
\n\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 < 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 >= 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 >= 1) ? hashes[left - 1] : 0)) % kMod;\n  }\n};\n\n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"
Summary Rolling hash is a common technique to compare if two substrings are equal or not. Given O(n) preprocessing time, the comparison becomes O(1) at the best case. OJ Details We use two large coprime numbers for base and for mod. We use a polynomial to calculate the hash value. Typical values are and  …<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[48,54],"tags":[],"class_list":["post-1098","post","type-post","status-publish","format-standard","hentry","category-alg","category-string"],"_links":{"self":[{"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/posts\/1098","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=1098"}],"version-history":[{"count":24,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/posts\/1098\/revisions"}],"predecessor-version":[{"id":1694,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/posts\/1098\/revisions\/1694"}],"wp:attachment":[{"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/media?parent=1098"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/categories?post=1098"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/tags?post=1098"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}