# Rolling Hash

> [time=Fri, Aug 8, 2025 10:06 PM]

本文假設讀者知道什麼是Rolling Hash and Rabin-Karp algorithm。可以看這個影片教的很好 [Link](https://www.youtube.com/watch?v=5rrWmGBB0Xo&t=1542s)

## 筆記

### pair hash

要看題目會不會刻意構造碰撞。有些題目出得很賊，逼得人一定得用pair hash。
如果遇到這種情況，可以左邊取$p=1e9+7$，右邊取$q=1e9+9$

兩個都是質數，根據[中國剩餘定理](https://zh.wikipedia.org/zh-tw/%E4%B8%AD%E5%9B%BD%E5%89%A9%E4%BD%99%E5%AE%9A%E7%90%86)，相當於對$pq$這個超大的數取模，幾乎不會碰撞。

### 不取模

也可以直接不取模，用`unsigned long long`或`unsigned __int128`，讓它自然溢出，相當於對$2^{64}$或$2^{128}$取模。

:::info
C++中，`unsigned`型別的溢出是自然的，不會報錯。但是`signed`的溢出是Undefined behavior，嚴格(雞婆)的編譯器會給runtime error。
:::

:::danger
C++中各種associative containers 對`ull`有支援，對`uint128`沒有。
:::

## Luogu, P3370 【模板】[字串哈希](https://www.luogu.com.cn/problem/P3370)

直接套模板就好。

:::spoiler

#include <bits/stdc++.h>
using namespace std;
using ull = unsigned long long;
ull pows[1505];
ull base = 31;
int val(char c) {
    if ('a' <= c && c <= 'z') return (c-'a'+1);
    else if ('A' <= c && c <= 'Z') return 26 + (c-'A'+1);    
    return 52 + (c-'0');
}
ull shash(string& s) {
    ull ans = 0;
    for (char c : s) ans = ans*base + val(c);
    return ans;
} 
int main() {
    pows[0]=1;
    for (int i=1;i<1505;i++) pows[i] = pows[i-1]*base;
    int n; cin >> n;
    unordered_set<ull> has;
    for (int i=0;i<n;i++) {
        string s; cin >> s;
        has.emplace(shash(s));
    }
    cout << has.size();
}

:::

## Leetcode, [30. Substring with Concatenation of All Words](https://leetcode.com/problems/substring-with-concatenation-of-all-words/description/)

todo

## Leetcode, [3327. Check if DFS Strings Are Palindromes](https://leetcode.com/problems/check-if-dfs-strings-are-palindromes/description/)

難度分2454
解決完postorder的問題後，我們就只要解決
> 給定`s`，請在$O(1)$內回答`is s[l,r] palindromic?`

的問題，就AC了。

這一題`ull`自然溢出就可以。
以下這個代碼，速度上無情打敗98.04%
順帶一提，改成`uint128`變成打敗60%
:::spoiler

using ull = unsigned long long;
bool inited = false;
ull pows[100005];
void init() {
    if (inited) return;
    inited = true;
    pows[0]=1;
    for (int i=1;i<100005;i++) pows[i]=31*pows[i-1];
}
class Solution {
public:
    vector<vector<int>> G;
    vector<pair<int,int>> semmp;
    string s;
    string d0;
    void dfs(int loc = 0) {
        semmp[loc].first = d0.size();
        for (int next : G[loc]) {
            dfs(next);
        }
        d0 += s[loc];
        semmp[loc].second = d0.size();
    }
    vector<bool> findAnswer(vector<int>& parent, string& s) {
        init();
        int n = parent.size();
        this->s = s;
        G.resize(n);
        semmp.resize(n);
        for (int i=1;i<n;i++) {
            G[parent[i]].emplace_back(i);
        }
        dfs();
        vector<bool> ans(n);
        vector<ull> pre(n+1), repre(n+1);
        for (int i=1;i<=n;i++) {
            pre[i] = pre[i-1]*base + (d0[i-1]-'a'+1);
            repre[i] = repre[i-1]*base + (d0[n-i]-'a'+1);
        }
        for (int i=0;i<n;i++) {
            int l = semmp[i].first, r = semmp[i].second-1;
            ull sh = pre[r+1]-pre[l]*pows[r-l+1];
            ull revsh = repre[(n-1-l)+1]-repre[n-1-r]*pows[r-l+1];
            ans[i] = sh==revsh;
        }
        return ans;
    }
};

:::