<style>
.reveal .slides {
text-align: left;
font-size:30px;
}
</style>
# String Algorithm
Introduction to Competitive Programming
2024/05/29
----
- Trie
- Hash
- KMP
---
## Trie
字典樹(又稱字首樹)
----
## 結構
插入了「great」、「tea」、「ten」、「teddy」、「movie」、「moon」的字典樹
be like:
有了trie可以幹嘛？
----
----
## 引入問題
給 $N$ 個字串 $s_i$, 依序讀入後輸出
給 $Q$ 筆詢問，每次詢問給一個字串 $q_i$ ，回答有幾個字串是以 $q_i$這個字串為前綴的
暴力的做法 $\rightarrow$ $O(NQ \vert q_i\vert)$
trie $\rightarrow$ $O(Q \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
01trie
本質也是trie，通常遇到50%的xor題目都是用01trie解決
把每個數字二進制分解存進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 (N \le 10^5)$ 個數字
$Q (Q \le 10^5)$ 筆詢問，每次給你兩個數字 $v, d$
問序列中有多少個數字 xor $v$ 後 $\le d$
----
詢問多少個數字 xor $4$ 之後小於等於 $5$
----
----
----
----
----
### 區間最大 xor
給長度為 $N$ 的整數序列, 求出一個子區間其 xor 總和最大
- $1\le N\le 2\cdot 10^5$
----
先回到更簡單的題目, 給一個整數序列 $a$ 和整數 $d$
詢問序列中哪個數字與 $d$ xor 後最大?
此問題我們可以把先把 $a$ 中的所有數字丟進去 trie 裡面,
再 greedy 的每次往 xor 比較大的那邊走
----
而要求出區間最大 xor, 等價於把對於每個位置當右界
找出每個位置前綴 xor 中最大的那個
使用 trie 維護所有前綴總和即可
所有之中最大的為答案
---
## 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>
----
會發現過程中，有很多不必要的匹配
----
<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>
----
<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>
每次失敗就要重頭開始嘗試匹配
----
在匹配失敗時，前面已經有一段不用重新匹配
我們只需要從那之後開始匹配即可
<div style="font-size:60px">
`0123456789012`
`ab`<span style="color:green">abc<u>`ab`</u></span><span style="color:red">`a`</span>`bcabd`
<span style="color:green"><u>`ab`</u>cab</span><span style="color:red">`d`</span>
`^`
</div>
----
從第3個字元開始匹配
<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>
再次匹配失敗，把字串移動到必要的匹配上
----
從第1個字元開始匹配
<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>
----
## 次長相同前綴後綴
可以知道最長相同前綴後綴是字串自己本身
而我們要求的是次長，以 `abcabd` 為例
| 字串 | 次長相同前綴後綴 |
| --- | ------------- |
|`a` | $\phi$
|`ab` | $\phi$
|`abc` | $\phi$
|<u>`a`</u>`bc`<u>`a`</u> | `a`
|<u>`ab`</u>`c`<u>`ab`</u> | `ab`
|`abcabd` | $\phi$
----
## failure function
則當匹配失敗時，取其次長相同前綴後綴，
則可以直接移動詢問字串 `W` 到還未匹配過的位置
```python
while 還沒比對到最後一個字元:
if 比對字元成功:
比對下一個字元
else if 比對字元失敗:
取其次長相同前綴後綴，移動字串 W
else if 成功匹配整個字串:
紀錄答案，並且取其次長相同前綴後綴，移動字串 W
```
----
為了實作方便，
會將儲存次長相同前綴後綴最後一個字元的 index (0-base)
| 字串 | 次長相同前綴後綴index |
| --- | ------------- |
|`a` | $-1$
|`ab` | $-1$
|`abc` | $-1$
|<u>`a`</u>`bc`<u>`a`</u> | $0$
|<u>`ab`</u>`c`<u>`ab`</u> | $1$
|`abcabd` | $-1$
如果為空字串則為 `-1`，第一個 index 為 `0`，所以設前一個 `0-1 = -1`
----
## 程式碼
```cpp=
int failure[MXN]; //儲存以第i個為結尾的次長相同前綴後綴
void KMP(string s, string w){
// i 為字串 s 當前 index, j 為字串 w 以匹配到的 index
for(int i = 0,j = -1; i < s.size(); ++i){
while(j >= 0 && s[i] != w[j+1]){ // 當匹配失敗找到次長相同前綴後綴，移動字串W
j = failure[j];
}
if(s[i] == w[j+1]){ // 當字元相等
++j;
}
if(j+1 == w.size()){ // 當字串完全匹配
ans.push_back(i-w.size()+1); // 加進答案
j = failure[j]; // 移動字串W
}}}
```
----
## build
建 次長相同前綴後綴表
當一個字串想要加長 次長相同前綴後綴
則需在最尾端加上一個跟前綴下一個字元相同的字元
如果下一個相同代表可以加長，否則需要回到當前的次長相同前綴後綴
<u>ab</u>cc<u>ab</u> $\to$ <u>ab<span style="color:red">c</span></u>c<u>ab<span style="color:red">c</span></u>
----
因此當我們求出前 $i$ 個字元的次長相同前綴後綴，
如果想要求 $i+1$ 的次長相同前綴後綴
則是看原本的位置指到字元能不能加長
如果相同則可以加長
否則則找次長相同前綴後綴
----
## 程式碼
```cpp=
int failure[MXN];
void build_failure(string& w){
for(int i=1,j=fauilre[0]=-1;i<w.size();i++){
while(j>=0 && w[i] != w[j+1]){ //當不相同無法匹配
j = failure[j];
}
if(w[i] == w[j+1]){ // 如果可以加長長度，則為前一個答案+1
++j;
}
failure[i] = j; // 紀錄答案
}
}
```
----
## 複雜度
### build failure table
字元兩兩比對次數最多 $2 |W|$ 次
比對成功，長度增長；比對失敗，長度減短。總共增長 $|W|$ 次、最多減短 $|W|$ 次。邊框長度最多變動 $2 |W|$ 次
### search word
字元兩兩比對次數最多 2|S| 次
原理同上
複雜度 $O(|W|+|S|)$
---
休息
---
## Hash
中文叫雜湊
雜湊函式 (hash function) 把資料壓縮，使得資料量變小，將資料的格式固定下來。該函式將資料打亂混合，重新建立一個叫做雜湊值。雜湊值通常用一個短的隨機字母和數字組成的字串來代表
----
### rolling 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 範圍
因此通常會進行 mod 後再儲存
----
$p$ 通常大於值域的質數降低碰撞機率 ( ex: 13331, 14341, 75577)
mod 為模數，通常選質數降低碰撞機率，選約為 $10^9$ 附近的數字避免計算過程溢位
(ex: $10^9$+7, 998244353,999888733 )
可以把一些質數放[模板](https://github.com/jakao0907/CompetitiveProgrammingCodebook/blob/master/math/primes.cpp)以被不時之需
----
## 建表
建表部分會建每一個前綴字串的 Hash 值
$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=
const ll P = 75577;
const ll MOD = 998244353;
ll Hash[MXN]; //Hash[i] 為字串 [0,i] 的 hash值
void build(const string& s){
int val = 0;
for(int i=0; i<s.size(); i++){
val = (val * P %MOD + s[i]) % MOD;
Hash[i] = val;
}
}
```
----
建完表了，要怎麼獲得任意子字串的 Hash 值呢？
----
## 獲得子字串 $[l,r]$ 的 Hash 值
根據前面的 Hash 值定義
$[l,r]$ 的 Hash 值為
$H_{l,r} = (s_l * p^{r-l+1} + s_{l+1} * p^{r-l} + s_{l+2} * p^1 + ... +s_r * p^0)$ % mod
$\to (H_r - H_{l-1} * p^{r-l+1})$
當然 $O(n)$ 太慢了，可以根據前面的$H$前綴 $O(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=
const ll P1 = 75577;
const ll P2 = 12721; // 多一個質數 p2
const ll MOD1 = 998244353;
pair<ll,ll> Hash[MXN]; //Hash[i] 為字串 [0,i] 的 hash值
void build(const string& s){
pair<ll,ll> val = make_pair(0,0);
for(int i=0; i<s.size(); i++){
val.first = (val.first * P1 + s[i]) % MOD;
val.second = (val.second * P2 + s[i]) % MOD;
Hash[i] = val;
}
}
```
----
## 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"
----
因此具有單調性可以使用二分搜!
二分搜尋最長回文半徑 $r$，
每次判斷以每個字元為中心且半徑為 $r$ 的字串是否為回文
如果是回文，則代表此字串最長回文半徑至少為 $r$
不是回文則代表此字串最長回文半徑小於 $r$
檢查是否為回文可以用 hash $O(1)$ 判斷
----
而回文也分為兩種，長度為奇數或偶數
若為奇數，中心點為字元 "abcba"
若為偶數，中心點為空白 "abba"
所以檢查時兩種情況(中心為字元或空白)都要檢查
----
## 複雜度
對於每個位置當成中心點, 二分搜最長回文長度
每個字元或空白為中心且半徑為 $r$ 的字串是否為回文
總共 $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$ 的冪次反過來建表
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]$
如此一來修改某個元素時, 對於所有 Hash[$i:n$] s[i] 乘上的冪次都會相同不影響
----
區間修改從 $i$ 開始到結尾的
因此我們可以使用 BIT 等資料結構來維護區間加值
使用 BIT 記得要 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);
}
```
----
### 總複雜度
修改 $O(\log N)$
詢問 $O(\log N)$
---
## 期末考資訊
下星期三 6/5 18:30-23:00
8-10 題
個人賽，不提供記分板
範圍: 期中考後到這周的主題
提供模板(會在DC公告)
----
作業連結：[link](https://vjudge.net/contest/628772)
Deadline: 06-09 00:00
{"title":"String Algorithm","slideOptions":"{\"transition\":\"fade;\"}","contributors":"[{\"id\":\"08326fa4-ca9b-4ca9-873e-239ebe76662c\",\"add\":22073,\"del\":658},{\"id\":\"19f09ccf-6b99-452f-971f-955cfc1657f3\",\"add\":89,\"del\":0}]","description":"Introduction to Competitive Programming"}