【模板】字符串哈希（String Hash）
===

字符串的比較很慢，因此我們把一個字符串映射到整數。那麼我們可以很方便的比較字串是否相等。

Hash 的核心思想是把輸入映射到一個值域比較小的範圍，方便我們做比較。因為哈希函數是一個多對少的函數映射，因此：

- 如果兩輸入的哈希值不同，那他們一定不同
- 如果兩輸入的哈希值相同，那他們可能相同（也可能不同，我們稱為碰撞。我們希望碰撞的概率很小）

我們通常這樣定義 Hash 函數，用於字符串哈希：

$$
\begin{align}
h(s) &= s[0] b^{n-1} + s[1]b^{n-2} + \dots + s[n-1]b^0 &\mod M \\
&= \sum_{i=0}^{n-1} s[i]\times b^{n-i-1} &\mod M
\end{align}
$$

我們可以想像成把字符串 $s$ 轉成一個 $b$ 進位的係數，每一位的值是 $s[i]$。而字串開頭在高位，字串結尾在低位。最後的結果需要模一個質數。

我們通常選擇 $M$ 為一個盡量大的質數，$b$ 為一個比最大字符大的質數。

const int M = 1e9 + 7;
const int B = 233;

typedef long long ll;

int get_hash(const string& s) {
  int res = 0;
  for (int i = 0; i < s.size(); ++i) {
    res = ((ll)res * B + s[i]) % M;
  }
  return res;
}

bool cmp(const string& s, const string& t) {
  return get_hash(s) == get_hash(t);
}

## 子串哈希

單次計算一個字符串的哈希值，$O(n)$ 的時間，我們不如直接暴力匹配。但哈希的好處是，我們可以快速取的一個子串的哈希值。

我們採取前綴和的思想，首先對每個前綴預處理出哈希值，再想辦法從兩個前綴湊出區間答案。我們令前綴的哈希值：

$H(i) = h(s[0:i)\,)$

怎麼快速計算出 $H(i)$ 呢？

$$
\begin{align}
H(i-1) &= s[0]b^{i-2} + s[1]b^{i-3} + \dots + s[i-2]b^0 &\mod M \\
H(i) &= s[0]b^{i-1} + s[1]b^{i-2} + \dots + s[i-2 ]b^1 + s[i-1]b^0 &\mod M
\end{align}
$$

可以觀察到：

$$
H(i) = H(i-1) \times b + s[i-1] \mod M
$$

因此，我們可以 $O(n)$ 計算出每個前綴的哈希值。

現在，我們想要求出：

$$
h(s[l:r)) = s[l]b^{r-l-1}+ \dots + s[r-1]b^0 \mod M
$$

我們可以拿 $H(r)$ 扣掉前面多餘的部分： $s[0]^{r-1}+ \dots + s[l-1]b^{r-l}$。

這一段字符串的資訊在 $H(l)$ 裡，差了 $b^{r-l}$ 倍，只要乘回去就好了。因此我們可以得出：

$$
h(s[l:r)) = H(r) - H(l) \times b^{r-l} \mod M
$$

## 練習

[【模板】manacher 算法 - 洛谷](https://www.luogu.com.cn/problem/P3805)