<style>
.reveal .slides {
text-align: left;
font-size:30px;
}
</style>
# String Algorithm
Introduction to Competitive Programming
2025/05/22
----
- Trie
- KMP
- Hash
---
## Trie
字典樹(又稱字首樹)
----
## 結構
插入了「great」、「tea」、「ten」、「teddy」、「movie」、「moon」的字典樹
be like:
有了trie可以幹嘛？
----
----
## 引入問題
給 $N$ 個字串 $s_i$, 依序讀入後輸出
給 $Q$ 筆詢問，每次詢問給一個字串 $q_i$ ，回答有幾個字串是以 $q_i$這個字串為前綴的
暴力的做法 $\rightarrow$ $O(N \sum \vert q_i\vert)$
trie $\rightarrow$ $O(\sum \vert q_i\vert)$
----
## trie的宣告
<div style="font-size: 30px">
每個節點有往下的指標
以及紀錄多少個字串以此為結尾
</div>
```cpp=
struct trie{
trie *nxt[26];
int cnt; //紀錄有多少個字串以此節點結尾
int sz; //有多少字串的前綴包括此節點
trie():cnt(0),sz(0){
memset(nxt,0,sizeof(nxt));
}
};
//創建新的字典樹
trie *root = new trie();
```
所以根節點到某一個節點的這條路就會是一個字串
根節點到根節點的意思就是空字串
----
### 插入
將字串 $s$ 加入字典樹
```cpp=
// O(|s|)
void insert(string& s){
trie *now = root; // 每次從根結點出發
for(auto i:s){
now->sz++;
if(now->nxt[i-'a'] == NULL){
now->nxt[i-'a'] = new trie();
}
now = now->nxt[i-'a']; //走到下一個字母
}
now->cnt++;
now->sz++;
}
```
----
可以用sz判斷有多少字串的前綴包括此節點
<center>
</center>
----
用cnt判斷字典樹上是否存在某個特定字串
<center>
</center>
----
### 查詢
```cpp=
// O(|s|)
int query_prefix(string& s){ //查詢有多少前綴為 s
trie *now = root; // 每次從根結點出發
for(auto i:s){
if(now->nxt[i-'a'] == NULL){
return 0;
}
now = now->nxt[i-'a'];
}
return now->sz;
}
int query_count(string& s){ //查詢字串 s 出現次數
trie *now = root; // 每次從根結點出發
for(auto i:s){
if(now->nxt[i-'a'] == NULL){
return 0;
}
now = now->nxt[i-'a'];
}
return now->cnt;
}
```
---
## bitwise trie
01 trie
本質也是trie。
只不過是把每個數字變成二進制的形式(一條 bitstring)存進trie裡面
----
從最高位元開始存，由根結點往下存數字
每個點分成 0 和 1 兩個子節點
定義左邊是 0 右邊是 1
<center>
</center>
----
## 0 1 trie的宣告
<div style="font-size: 30px">
每個節點有往下的指標
以及紀錄多少個字串以此為結尾
</div>
```cpp=
struct trie{
trie *nxt[2];
int cnt; //紀錄有多少個字串以此節點結尾
int sz; //有多少字串的前綴包括此節點
trie():cnt(0),sz(0){
memset(nxt,0,sizeof(nxt));
}
};
//創建新的字典樹
trie *root = new trie();
```
----
### 插入
將數字 $x$ 加入字典樹，$O(\log x)$
```cpp=
void insert(int x){
trie *now = root; // 每次從根節點開始
for(int i=30;i>=0;i--){ // 從最高位元開始往低位元走
now->sz++;
if(now->nxt[x>>i&1] == NULL){ //判斷當前第 i 個位元是 0 還是 1
now->nxt[x>>i&1] = new trie();
}
now = now->nxt[x>>i&1]; //走到下一個位元
}
now->cnt++;
now->sz++;
}
```
----
### 引入問題
一開始給 $N$ 個數字
$Q$ 筆詢問，每次給你兩個數字 $v, d$
問序列中有多少個數字 xor $v$ 後 $\le d$
- $N,Q \leq 10^5$
----
詢問多少個數字 xor $4$ 之後小於等於 $5$ ?
你會發現如果有某個數字在最左邊的 bit 是 1，那他 xor 4 後會成 0XX，也就是一定會小於 5
----
也就是從這個 1 節點連下去的所有數字 xor 4 都會 $<5$ (所以該節點的 sz 可以全部貢獻給答案 )
但左邊不一定，所以要往 v[i] xor d[i] 的那個點往下走
<!-- ---- -->
<!--  -->
----
----
----
----
----
### 區間最大 xor
給長度為 $N$ 的整數序列, 求出一個子區間其 xor 總和最大
- $1\le N\le 2\cdot 10^5$
----
先回到更簡單的題目, 給一個整數序列 $a$ 和整數 $d$
詢問序列中哪個數字與 $d$ xor 後最大?
此問題我們可以把先把 $a$ 中的所有數字丟進去 trie 裡面,
再 greedy 的每次往 xor 比較大的那邊走也就是 比較高位的 bit xor 後是 1 的
----
所以當序列 $a$ 是原序列的前綴 xor
這時候對於每個位置的 $a[i]$ (a[0~i-1] 已被插入 trie)
去查詢 greedy 的找就能找到 使得 a[i] ^ a[j] (j < i) 最大的 $j$ ，此時最大區間就是 $(j,i]$
---
## Knuth–Morris–Pratt algorithm
### (KMP)
$O(\vert T \vert + \vert S \vert)$算出字串 T 在字串 S 中出現的所有位置
$1 \leq \vert T \vert , \vert S \vert \leq 10^6$
----
## 暴力的作法
枚舉S的每個位置，檢查從這個位置開始長度為$\vert T \vert$的字串是否跟 T 一樣
複雜度：$O(\vert T \vert \cdot \vert S \vert) \rightarrow$ TLE
----
<!-- ## Hash作法
用rolling hash預處理所有長度為$\vert T \vert$的子字串Hash值
判斷每個位置的Hash值是否跟 $T$ 的Hash值相等
$O(\vert T \vert + \vert S \vert)$
---- -->
### 暴力作法
<div style="font-size:60px">
`S` = ababcababcabd
`W` = abcabd
</div>
----
比對第一個字元相同
<div style="font-size:60px">
`0123456789012`
<span style="color:green">a</span>`babcababcabd`
<span style="color:green">a</span>`bcabd`
`^`
</div>
----
比對第二個字元相同
<div style="font-size:60px">
`0123456789012`
<span style="color:green">ab</span>`abcababcabd`
<span style="color:green">ab</span>`cabd`
`^`
</div>
----
比對第三個字元相異
<div style="font-size:60px">
`0123456789012`
<span style="color:green">ab</span><span style="color:red">`a`</span>`bcababcabd`
<span style="color:green">ab</span><span style="color:red">`c`</span>`abd`
`^`
</div>
----
把 `W` 字串往右一格重新比對，比對失敗
<div style="font-size:60px">
`0123456789012`
`a`<span style="color:green"></span><span style="color:red">`b`</span>`abcababcabd`
<span style="color:green"></span><span style="color:red">`a`</span>`bcabd`
`^`
</div>
----
再把 `W` 字串往右一格重新比對，第一格相同
<div style="font-size:60px">
`0123456789012`
`ab`<span style="color:green">a</span><span style="color:red"></span>`bcababcabd`
<span style="color:green">a</span><span style="color:red"></span>`bcabd`
`^`
</div>
----
比對第二格相同
<div style="font-size:60px">
`0123456789012`
`ab`<span style="color:green">ab</span><span style="color:red"></span>`cababcabd`
<span style="color:green">ab</span><span style="color:red"></span>`cabd`
`^`
</div>
----
比對第三格相同
<div style="font-size:60px">
`0123456789012`
`ab`<span style="color:green">abc</span><span style="color:red"></span>`ababcabd`
<span style="color:green">abc</span><span style="color:red"></span>`abd`
`^`
</div>
----
比對第四格相同
<div style="font-size:60px">
`0123456789012`
`ab`<span style="color:green">abca</span><span style="color:red"></span>`babcabd`
<span style="color:green">abca</span><span style="color:red"></span>`bd`
`^`
</div>
----
比對第五格相同
<div style="font-size:60px">
`0123456789012`
`ab`<span style="color:green">abcab</span><span style="color:red"></span>`abcabd`
<span style="color:green">abcab</span><span style="color:red"></span>`d`
`^`
</div>
----
比對第六格相異
<div style="font-size:60px">
`0123456789012`
`ab`<span style="color:green">abcab</span><span style="color:red">`a`</span>`bcabd`
<span style="color:green">abcab</span><span style="color:red">`d`</span>
`^`
</div>
----
再把 `W` 字串往右一格重新比對，第一格相異
<div style="font-size:60px">
`0123456789012`
`aba`<span style="color:green"></span><span style="color:red">`b`</span>`cababcabd`
<span style="color:green"></span><span style="color:red">`a`</span>`bcabd`
`^`
</div>
----
再把 `W` 字串往右一格重新比對，第一格相異
<div style="font-size:60px">
`0123456789012`
`abab`<span style="color:green"></span><span style="color:red">`c`</span>`ababcabd`
<span style="color:green"></span><span style="color:red">`a`</span>`bcabd`
`^`
</div>
----
再把 `W` 字串往右一格重新比對，第一格相同
<div style="font-size:60px">
`0123456789012`
`ababc`<span style="color:green">a</span><span style="color:red"></span>`babcabd`
<span style="color:green">a</span><span style="color:red"></span>`bcabd`
`^`
</div>
----
第二格相同
<div style="font-size:60px">
`0123456789012`
`ababc`<span style="color:green">ab</span><span style="color:red"></span>`abcabd`
<span style="color:green">ab</span><span style="color:red"></span>`cabd`
`^`
</div>
----
第三格相異
<div style="font-size:60px">
`0123456789012`
`ababc`<span style="color:green">ab</span><span style="color:red">`a`</span>`bcabd`
<span style="color:green">ab</span><span style="color:red">`c`</span>`abd`
`^`
</div>
----
再把 `W` 字串往右一格重新比對，第一格相異
<div style="font-size:60px">
`0123456789012`
`ababca`<span style="color:green"></span><span style="color:red">`b`</span>`abcabd`
<span style="color:green"></span><span style="color:red">`a`</span>`bcabd`
`^`
</div>
----
再把 `W` 字串往右一格重新比對，第一格相同
<div style="font-size:60px">
`0123456789012`
`ababcab`<span style="color:green">a</span><span style="color:red"></span>`bcabd`
<span style="color:green">a</span><span style="color:red"></span>`bcabd`
`^`
</div>
----
第二格相同
<div style="font-size:60px">
`0123456789012`
`ababcab`<span style="color:green">ab</span><span style="color:red"></span>`cabd`
<span style="color:green">ab</span><span style="color:red"></span>`cabd`
`^`
</div>
----
第三格相同
<div style="font-size:60px">
`0123456789012`
`ababcab`<span style="color:green">abc</span><span style="color:red"></span>`abd`
<span style="color:green">abc</span><span style="color:red"></span>`abd`
`^`
</div>
----
第四格相同
<div style="font-size:60px">
`0123456789012`
`ababcab`<span style="color:green">abca</span><span style="color:red"></span>`bd`
<span style="color:green">abca</span><span style="color:red"></span>`bd`
`^`
</div>
----
第五格相同
<div style="font-size:60px">
`0123456789012`
`ababcab`<span style="color:green">abcab</span><span style="color:red"></span>`d`
<span style="color:green">abcab</span><span style="color:red"></span>`d`
`^`
</div>
----
第六格相同，找到一組解
<div style="font-size:60px">
`0123456789012`
`ababcab`<span style="color:green">abcabd</span><span style="color:red"></span>
<span style="color:green">abcabd</span><span style="color:red"></span>
`^`
</div>
----
會發現過程中，有很多不必要的匹配
----
沒有，我沒發現
KMP 很難懂，但我個人理解的方式是用前綴函數理解的。
----
對於一個字串 $s$
我們定義他的前綴函數為
$\pi[i] = 最大的 \ k < i \ 使得 s[0...k] = s[i-k...i]$
這其實就是次長相同前後綴的長度
----
## 次長相同前綴後綴
可以知道最長相同前綴後綴是字串自己本身
而我們要求的是次長，以 `abcabd` 為例
|$i$| 字串 | 次長相同前綴後綴 | $\pi[i]$ |
|-- | --- | ------------- | ----- |
|$0$|`a` | $\phi$ | $0$
|$1$|`ab` | $\phi$ | $0$
|$2$|`abc` | $\phi$ | $0$
|$3$|<u>`a`</u>`bc`<u>`a`</u> | `a`| $1$
|$4$|<u>`ab`</u>`c`<u>`ab`</u> | `ab`| $2$
|$5$|`abcabd` | $\phi$| $0$
----
假設如果我們有辦法造出這個，前綴函數$\ \pi$ 那麼在字串 $S$ 中找到 $T$ 出現的所有位置的問題就能這樣做:
我們構造一個新字串 $W=T+$'@'$+S$，其中 '@' 要是一個不在 $S$ 也不在 $T$ 中出現的任意字元。
這時如果對 $W$ 求前綴函數 $\pi$，你會發現當 $\pi[i]=|T|$ 時，這時候次長相同前綴後綴就會長
----
這樣
你會發現這恰好是 $T$ 在 $S$ 出現的地方(不過這是尾巴，通常會需要開頭，這時候記得要記 $i-|T|+1$ 而不是 $i$)。
並且他一定是 $T$ 出現在 $S$ 的地方
----
因為如果 $\pi[i]$ 想要更大，也就是 $\pi[i]\rightarrow \pi[i]+1$
那麼 $?$ 處就得是 @，但 @ 不在 $S$ 或 $T$ 內出現過，所以這不可能。
----
求前綴函數:
假設我們知道 $0 \cdots i$ 的 $\pi$ 值，想求 $i+1$ 處的 $\pi$ 值時
假設兩個 ? 處都是相等的字元，那 $\pi[i+1]$ 就可以是 $\pi[i]+1$
----
那有沒有可能會比 $\pi[i]+1$ 大?
那你會發現此時 $\pi[i]$ 就要跟著變大，所以不可能。
----
那假如兩個 ? 處不相等呢,它一定就比 $\pi[i]+1$ 小
也就是找到某個比黃條還小的藍框 (如圖) ，然後再去檢查藍框對前綴的位置$+1$ (也就是圖上的第一個 ? ) 和後面的那個 ? 是否相等 (如果不是就繼續找更小的藍框)，此時$\pi [i+1]=$藍框長度$+1$。
----
這藍框怎麼找? 你會發現兩段黃色的字串是一模一樣的 (依照定義)，所以找藍色的相當於找大字串的前綴字串內的次長相同前後綴
也就是 $\pi[\pi[i]-1]$
所以我們只要找到一個最大的藍框使得兩個問號處是相等的，那就能作為 $\pi[i+1]$ 的答案
----
### 計算前綴函數
```cpp=
//pi[i] = 最大的 k 使得 s[0...(k-1)] = s[i-(k-1)...i]
vector<int> prefunc(const string& s){
int n = s.size();
vector<int> pi(n);
for(int i=1,j=0;i<n;++i){
j = pi[i-1];
while(j && s[j] != s[i]) j = pi[j-1]; //往下找藍框
if(s[j] == s[i]) ++j; //相等會多一格
pi[i] = j;
}
return pi;
}
```
複雜度 $O(n)$ 很直觀的均攤，因為第二圈能跑的次數會跟 stack 去做 pop 一樣(前面有人++才能在後面被--)，考慮 $++j$ 是一種 insert 那你可以把它看成，對於每個字元 $s[i]$ 只會進出隊至多一次，所以是 $O(n)$。
----
有了前綴函數，就能實現 KMP 了
第一種方式就是前文提到的中間放個 @
```cpp=
//找出 T 在 S 中出現的所有位子
vector<int> kmp(string S, string T) {
string W = "";
W+=T,W+='@',W+=S;
vector<int> pi = prefunc(W);
vector<int> ans;
for (int i = T.size(); i < W.size(); i++) {
if (pi[i] == T.size()) {
ans.push_back(i - T.size() + 1);
}
}
return ans;
}
```
----
第二種方式(不併字串)，就是用前綴函數找藍框那招
```cpp=
//找 s 在 str 中出現的所有位子
vector<int> kmp(string str, string s) {
vector<int> nxt = prefunc(s);
vector<int> ans;
for (int i = 0, j = 0; i < SZ(str); i++) {
while (j && str[i] != s[j]) j = nxt[j - 1];
if (str[i] == s[j]) j++;
if (j == SZ(s)) {
ans.push_back(i - SZ(s) + 1);
j = nxt[j - 1];
}
}
return ans;
}
```
---
休息
---
## Hash
中文叫雜湊
雜湊函式 (hash function) 用途在把值域太大的鍵值 (沒辦法直接存) 壓到一個較小的值域使得鍵值能夠在常數時間比對/存取。
----
[My grandmother run faster than your code](https://youtu.be/314OLE6mKOo?si=MC3giAV3ra0WCTLb&t=127)
----
### String Hash
選一個整數 $p$ , 把字串轉換成 $p$ 進位的數字來儲存
原本字串比對是否相同需要 $O(|S|)$, 轉換成數字比較是否相同只需要 $O(1)$ 的時間
----
S = "ABCA" 為例, 轉成 $p$ 進位
則會變成 $A\cdot p^3 + B\cdot p^2 + C\cdot p^1 + A \cdot p^0$
而當字串非常長的時, 轉換會超出 long long 範圍 (也就是值域太大的問題)
所以根據 hash 的精神我們就 mod 一個可以被存下的數字 (打到小值域)
----
$p$ 你就挑一個大小適中的質數 (不要挑甚麼 $2$ 這種) ( ex: 13331, 14341, 75577)
也不要挑太大很容易乘出循環 (畢竟要 mod)
mod 為模數，通常選質數以降低碰撞機率，選約為 $10^9$ 附近的數字避免計算過程溢位 (平方後 $< 10^{18}$ )
(ex: $10^9$+7, 998244353,999888733 )
可以把一些質數放[模板](https://github.com/jakao0907/CompetitiveProgrammingCodebook/blob/master/math/primes.cpp)以備不時之需
----
## Rolling Hash
滾動式的去計算 hash ，主要是實作方便，我們後面會看到不 rolling 的例子
$H_{0,k}$ 為字串 $s[0,k]$ hash 出來的結果
$H_{0,k} = (s_0\cdot p^k + s_1\cdot p^{k-1} + s_2\cdot p^{k-2} ... + s_k\cdot p^0)$ % mod
$\to H_{0,0} = (s_0\cdot p^0)$ % mod
$\to H_{0,1} = (H_{0,0}\cdot p + s_1)$ % mod
$\to H_{0,2} = (H_{0,1}\cdot p + s_2)$ % mod
$\to H_{0,i} = (H_{0,i-1}\cdot p + s_i)$ % mod
----
s="XDDCC"
$\to H_{0,0} = (X\cdot p^0)$ % mod
$\to H_{0,1} = (X\cdot p^1 + D\cdot p^0)$ % mod
$\to H_{0,2} = (X\cdot p^2 + D\cdot p^1 +D\cdot p^0)$ % mod
$\to H_{0,3} = (X\cdot p^3 + D\cdot p^2 +D\cdot p^1 + C\cdot p^0)$ % mod
$\to H_{0,4} = (X\cdot p^4 + D\cdot p^3 +D\cdot p^2 + C\cdot p^1 + C\cdot p^0)$ % mod
----
建立所有前綴的 Hash 值 $H_{[0:k]}$
```cpp=
using i64 = long long;
const i64 P = 75577;
const i64 MOD = 998244353;
i64 Hash[MXN]; //Hash[i] 為字串 [0,i] 的 hash值
void build(const string& s){
i64 val = 0;
for(int i = 0; i < s.size(); i++){
val = (val * P %MOD + s[i]) % MOD;
Hash[i] = val;
}
}
```
----
## 獲得子字串 $[l,r]$ 的 Hash 值
根據前面的 Hash 值定義
$[l,r]$ 的 Hash 值為
$H_{l,r} = (s_l * p^{r-l} + s_{l+1} * p^{r-l-1} + s_{l+2} * p^{r-l-2} + ... +s_r * p^0)$ % mod
當然 $O(n)$ 太慢了，可以根據前面算好的 $H$ $O(1)$ 計算
$\to (H_{0,r} - H_{0,l-1} * p^{r-l+1})$
----
s="XDDCC" 求[1,3]的 Hash 值
$H_{1,3} = (D\cdot p^2 +D\cdot p^1 + C\cdot p^0)$ % mod
$\to H_{0,0} = (X\cdot p^0)$ % mod
$\to H_{0,3} = (X\cdot p^3 + D\cdot p^2 +D\cdot p^1 + C\cdot p^0)$ % mod
可以觀察到 $H_{1,3}$ 可以 $O(1)$ 算出來
$H_{1,3} = H_{0,3} - H_{0,0} \cdot p^3$
----
透過 $O(n)$ 預處理前綴 Hash 表
就可以 $O(1)$ 得出某段子字串的 Hash 值
如果題目詢問兩段子字串是否一樣就可以用這個技巧 $O(1)$ 解決
----
## double hashing
遇到好好設計過的測資，在一定的條件下有機率讓選擇的 $p$ 和 $mod$ 做的 hash 發生碰撞
所以會選擇找另一個 $p_2$ 做雙重 hash ，讓每個區間有兩種 hash 值
----
```cpp=
#define ff first
#define ss second
using i64 = long long;
const i64 P1 = 75577;
const i64 P2 = 12721; // 多一個質數 p2
const i64 MOD = 998244353;
pair<i64,i64> Hash[MXN]; //Hash[i] 為字串 [0,i] 的 hash值
void build(const string& s){
pair<i64,i64> val(0,0);
for(int i=0; i < s.size(); i++){
val.ff = (val.ff * P1 + s[i]) % MOD;
val.ss = (val.ss * P2 + s[i]) % MOD;
Hash[i] = val;
}
}
```
此時字串要相等就得兩維 hash 要相等
----
## Longest Palindromic Substring
給定一個字串 $s (1 \le |s| \le 10^5)$，求所有的回文子字串中，長度最長為多少
"ababa" $\to$ 5
"caaabc" $\to$ 3
----
## brute force
暴力窮舉所有區間 $O(N^2)$
再花 $O(N)$ 時間檢查窮舉的區間是否為回文
複雜度 $O(N^3)$
----
## brute force with hash
hash 後可以花 O(1) 時間知道字串某個子區間的hash值
如果一個字串是回文，則字串本身與反過來會相同
先預處理
字串 $s$ 的 hash 值以及
反轉的字串 reverse($s$) 的 hash 值
則可以花 $O(1)$ 時間判斷字串是否為回文
複雜度 $O(N^3) \to O(N^2)$
----
## binary search with hash
但還可以更快
如果一個字串是回文，
把最左以及最右的字元刪掉也是回文
或者最左最右分別加上相同字元也是回文
s="abaaba"
同時刪除最左右 $\to$ "baab"
同時加上字元'c' $\to$ "cabaabac"
所以最長回文回文長度是否為 k 對 k 有單調性
----
二分搜尋最長回文長度 $r$，
$O(n)$ 跑一個 $r$ 長的滑窗
如果是回文，則代表此字串最長回文半徑至少為 $r$
不是回文則代表此字串最長回文半徑小於 $r$
檢查是否為回文可以用 hash $O(1)$ 判斷
----
## 複雜度
滑窗最多滑 $O(N)$ 二分搜 $O(\log N)$
複雜度 $O(N\log N)$
----
有些字串的題目都具有單調性使之可以二分搜尋
再搭配 hash，通常都可以做到 $O(N\log N)$ 的複雜度
----
## [Hash + 修改](https://cses.fi/problemset/task/2420)
給定一個字串, 兩種操作
1. 詢問區間 [l, r] 是否為回文
2. 修改第 $i$ 個字元
多了第二種操作 修改字元
----
可以發現我們 Hash[i] 儲存的是前綴 Hash 值
修改第 $i$ 個字元會影響到 Hash[i:n]
也就是從第 $i$ 個位置的 Hash 值到最後一個的 Hash 值
----
而原本 hash 的建法
Hash[2] = $p^2\cdot s[0] + p^1\cdot s[1] + p^0\cdot s[2]$
Hash[3] = $p^3\cdot s[0] + p^2\cdot s[1] + p^1\cdot s[2] + p^0\cdot s[3]$
會發現修改位置 2 則, 後面每格的 hash 值對於 s[2] 乘的 $p$ 冪次會不同
----
因此我們通常會把 $p$ 的冪次反過來建表
也就非 rolling hash
Hash[2] = $p^0\cdot s[0] + p^1\cdot s[1] + p^2\cdot s[2]$
Hash[3] = $p^0\cdot s[0] + p^1\cdot s[1] + p^2\cdot s[2] + p^3\cdot s[3]$
你會發現這樣的表示方式其實是比較直觀的 (index i 對應到的次方就是 i 次)
如此一來修改某個元素時, 對於所有 Hash[$i:n$] s[i] 乘上的冪次都會相同不影響
----
區間修改從 $i$ 開始到結尾的
因此我們可以使用 BIT 等資料結構來維護區間加值
使用 BIT 記得要 1-base (我都 -1 base),
可以在字串前面加上一個填充字元
----
從修改的位置 pos 加值, 加的值 為新字元與舊字元的差值 $\times p$ 的 pos 次方
所有 $p$ 的次方可以在一開始先 $O(N)$ 預處理
由於要求回文, 因此要儲存正反字串分別的 Hash 值
```cpp
void update(int pos, int ch){
BIT.update(pos, (ch - s[pos]) * p[pos] % MOD);
revBIT.update(n-1-pos, (ch-s[pos]) * p[n-pos-1] % MOD);
}
```
----
那為啥還需要 rolling hash?
因為不用 Modular Inverse
你會發現要求區間 [l,r] hash 時 $H_{r,0} - H_{l-1,0} = s[l]\cdot p^l + ... + s[r]\cdot p^r$
此時 $(H_{r,0} - H_{l-1,0})\cdot p^{-l}$ 才會是該區間的 hash 值，我覺得方便性因人而異。
----
### 總複雜度
修改 $O(\log N)$
詢問 $O(\log N)$
---
[題單](https://vjudge.net/contest/718351#overview)
{"title":"String Algorithm","slideOptions":"{\"transition\":\"fade;\"}","description":"Introduction to Competitive Programming","contributors":"[{\"id\":\"08326fa4-ca9b-4ca9-873e-239ebe76662c\",\"add\":19450,\"del\":0},{\"id\":\"c09566ae-e372-4be1-b467-1ebdd3589721\",\"add\":4464,\"del\":2951,\"latestUpdatedAt\":null}]"}