---
tags: Training, 2022WinterTraining
type: slide
slideOptions:
transition: fade;
---
<style>
.reveal .slides {
text-align: left;
font-size:30px;
}
</style>
# 字串演算法
#### 進階程式競賽技巧
#### 2022/12/2
----
- Suffix Array
- KMP
- Manacher
- Zvalue
- Palindromic Tree
---
## Suffix Array
### 後綴數組
簡稱 SA，將字串的所有後綴排序後的數組
----
主要有兩個數組：`SA[N]、H[N]`
----
## SA 數組
把字串的所有後綴排序後的結果
以字串 S = "babd" 為例
所有後綴有
"babd"
"abd"
"bd"
"d"
排序後為
"adb"
"babd"
"bd"
"d"
----
S = "babd"
而 SA[i] 存的就是第 $i$ 小的後綴是第幾個字元開始的字串
SA[0] = 1 ("abd")
SA[1] = 0 ("babd")
SA[2] = 2 ("bd")
SA[3] = 3 ("d")
----
## 複雜度
而如果直接做可以用 $O(N^2lgN)$ 做到
$O(NlgN)$ 排序，$O(N)$比較大小
但太慢了，至於快的作法...我也不會
模板作法複雜度 $O(N)$
----
## Height 數組
裡面儲存的值為第 $i$ 小的字串
跟第 $i-1$ 小的字串共同前綴長度 (簡稱LCP，Longest Common Prefix)
----
## Height 數組
跟第 $i-1$ 小的後綴字串的共同前綴長度
"adb"
"babd"
"bd"
"d"
H[0] = 0 (第0個字串沒有前一個)
H[1] = 0
H[2] = 1 ("b")
H[3] = 0
----
## Longest Common Substring
### 最長共同子字串
可以 $O(N^2)$ DP
A = "abaad"
B = "aada"
A 和 B 的最長共同子字串 (不是子序列)
為 "aad"
----
如果我們可以將兩個字串合併起來去做 SA
A = "abaad"
B = "aada"
求以上兩個字串的最長共同子字串
中間加沒出現過的字元合起來
S = "abaad@aada"
複雜度 $O(|A|+|B|)$
----
接著 SA 得到後綴數組
S = "abaad@aada"
| SA | Height |
|---| --- |
|"@aada" | 0 |
|"a" | 0 |
|"aad@aada" | 1 |
|"aada" | 3 |
|"abaad@aada"| 1 |
|"ad@aada" | 1 |
|"ada" | 2 |
|"baad@aada" | 0 |
|"d@aada" | 0 |
|"da" | 1 |
----
有了後綴數字，就看哪兩個連續的後綴字串為不同字串相間
然後取 max 即為答案
| SA | Height |
|---| --- |
|"@aada" | 0 |
|"a" | 0 |
|<span style="color:red">"aad@aada"</span> | 1 |
|<span style="color:red">"aada"</span> | 3 |
|"abaad@aada"| 1 |
|"ad@aada" | 1 |
|"ada" | 2 |
|"baad@aada" | 0 |
|"d@aada" | 0 |
|"da" | 1 |
----
## 應用 - 相異子字串數量
給定一個字串 `S` $( 1 \le |$`S`$| \le 10^6)$
求字串 `S` 中有幾個相異子字串
S = "aabaa"
所有相異子字串為
"a", "b", "aa", "ab", "ba", "aab", "aba", "baa",
"aaba", "abba", "aabaa"
----
透過 SA 求出 Height 數組
| SA | Height |
|---| --- |
|"a" | 0 |
|"aa" | 1 |
|"aabaa" | 2 |
|"abaa" | 1 |
|"baa" | 0 |
字串 S 總共有 |S| * (|S|+1) / 2 種子字串
Height 數組可以求出 LCP，LCP 代表連續兩個後綴字串重複的部分
全部子字串數量 - $\sum_{i=1}^{|S|} H_{i}$ 即為相異子字串數量
----
## 結合資料結構
給一個字串 $S ( 1 \le |S| \le 2 \cdot 10^5)$
$Q (1 \le Q \le 2 \cdot 10^5)$筆詢問
每筆詢問問你字串 `S` 中，以index $p$ 為開頭的後綴子字串與index $q$ 為開頭的後綴子字串的 LCP 長度是多少 ?
S = "abdabdaa"
以 index 0 與 index 3 為開頭的後綴子字串分別是
index 0 : "abdabdaa"
index 3 : "abdaa"
LCP 為 "abda" ，長度 4
----
透過 SA 求出 Height 數組後，
對於每筆詢問
求出兩個後綴在 SA 的位置，對這段區間的 Height 數組進行 RMQ求出 Height 的區間最小值，即可得到兩後綴的 LCP
----
S = "abaaba"
index 1("abaaba")為開頭的後綴，index 3("aaba")為開頭的後綴
| SA | Height |
|--- | ------ |
|"a" | 0 |
|"aaba" | 1 |
|"aba" | <span style="color:red">1 </span> |
|"abaaba" | <span style="color:red">3 </span> |
|"ba" | 0 |
|"baaba" | 2 |
即可得到兩後綴的 LCP
----
## 用法
[模板 SAIS.cpp](https://github.com/jakao0907/CompetitiveProgrammingCodebook/blob/master/string/SAIS.cpp)
傳入參數: ip 陣列放字串，len為字串長度
需保證 ip[len]為 0，且字串裡的元素不為 0
```cpp=
int H[ N ], SA[ N ]; // 會用到的數組在這
void suffix_array(int* ip, int len) {
// should padding a zero in the back
// ip is int array, len is array length
// ip[0..n-1] != 0, and ip[len] = 0
ip[len++] = 0;
sa.build(ip, len, 128);
for (int i=0; i<len; i++) {
H[i] = sa.hei[i + 1];
SA[i] = sa._sa[i + 1];
}
// resulting height, sa array \in [0,len)
}
```
---
## Knuth–Morris–Pratt algorithm
### (KMP)
給定一個原始字串 `S`，求出單字 `W` 在字串 `S` 中所有出現的位置
$1 \le$ | `W` | $\le$ | `S` | $\le 10^6$
----
## 暴力作法
`O(|S|*|W|)`
依序窮舉 `S` 每個位置為開頭的字串，花 `O(|W|)` 時間比對字串是否相同
----
<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(j-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|)$
---
## Manacher
### 馬拉車演算法
$O(N)$ 求以每個字元為中心的最長回文長度
----
## 作法
先將原始字串 S = "abaac"
頭尾以及每個字元間都加入一個沒出現過的字元，這邊以'@'為例
變成
"@a@b@a@a@c@"
----
原本要長度為偶數與長度為奇數的回文要分開出裡
"@a@b@a@a@c@"
但在每個中間加了一個字元後都會變成長度為奇數的回文
就可以一起處理了
實作細節不詳細介紹
----
[模板 zvalue_palindrome.cpp](https://github.com/jakao0907/CompetitiveProgrammingCodebook/blob/master/string/zvalue_palindrome.cpp)
s 為傳入的字串，len為字串長度，z為儲存答案的陣列
```cpp=
void z_value_pal(char *s,int len,int *z){
len=(len<<1)+1;
for(int i=len-1;i>=0;i--)
s[i]=i&1?s[i>>1]:'@';
z[0]=1;
for(int i=1,l=0,r=0;i<len;i++){
z[i]=i<r?min(z[l+l-i],r-i):1;
while(i-z[i]>=0&&i+z[i]<len&&s[i-z[i]]==s[i+z[i]])++z[i];
if(i+z[i]>r) l=i,r=i+z[i];
} }
```
----
## 答案
傳入一個長度為 $K$ 的字串，則會回傳一個長度為 $2K+1$ 的陣列 z
z 陣列儲存以每個字元為中心的回文半徑+1
s 原本為 abaac
變成
s = "`@a@b@a@a@c@`"
z = [`12141232121`]
---
## Z value
[模板](https://github.com/jakao0907/CompetitiveProgrammingCodebook/blob/master/string/zvalue.cpp)
如模板註解所寫 : z[i] = lcp(s[0:n-1], s[i:n-1])
void Z_value(const string& s)
複雜度 $O( |s| )$
----
z[i] = lcp(s[0:n-1],s[i:n-1])
void Z_value(const string& s)
丟進去字串 s，會把值存在陣列 z 裡面
其中第 $i$ 格存的東西為從第 $i$ 格開始的後綴子字串 s[i:n-1]
跟原始字串 s 的最長共同前綴
----
## 應用
### 搜尋字串 $S$ 裡面是否存在字串 $T$
如果把字串 S 跟 T 串起來
變成 $T$ + "@" + $S$ ("@" 為一個 S 和 T 都不會出現的字元)
如此一來如果丟進去 Z_value($T$ + "@" + $S$)
則只需找陣列 z 的區間 ( |T|+1, len-1 ) 裡是否存在某個值為 |T|，如果有代表有出現
----
## 應用
### 字串壓縮
對於字串 $S$，找出一個最短的字串 $T$，使得字串 $T$ 擴展 k 次可以變成 $S$
如 $S$ = "abcabcabcabc"，則 $T$ = "abc"
----
## 作法
先求出 z_value(S)
接者跑過所有 |S| 的因數 $k$，如果 k + z[k] = |S|
代表長度為 $k$ 的前綴可以擴展變成 S
以 "abababab" 為例
```
index = 0, 1, 2, 3, 4, 5, 6, 7
zvalue = 8, 0, 6, 0, 4, 0, 2, 0
k+z[k] = 8, 1, 8, 3, 8, 5, 8, 7
8 的因數 ↑ ↑ ↑
```
長度 1, 2, 4 是 |S| 的因數，其中 2+z[2], 4+z[4] 為 8
代表可以壓縮成長度 2, 4
---
## Palindromic Tree
### 回文樹
$O(N)$ 求以每個字元為結尾的最長回文長度以及相關資訊
----
[模板 PalTree2.cpp](https://github.com/jakao0907/CompetitiveProgrammingCodebook/blob/master/string/PalTree2.cpp)
裡面重要的有
state, len, num, cnt, fail
以上陣列
----
## state
所有以第 $i$ 個字元為結尾的最長回文都是一個state
而如果兩個不同字元為結尾的最長回文一樣，則他們state會一樣
而 state[i] 就是代表第 $i$ 個字元為結尾的最長回文
後面所有的東西都是用state去找資訊
----
## state 數組
state[i] 代表第 $i$ 個字元為結尾的最長回文編號
S = "abacaaba"
以第 2(0-base) 個字元為結尾的最長回文是 aba
以第 7(0-base) 個字元為結尾的最長回文是 aba
兩個最長回文都相同，因此 state[2] 會等於 state[7]
----
## len 數組
求出某個 state 的長度
S = "aababa"
len[state[1]] = 2 ("aa")
len[state[3]] = 3 ("aba")
len[state[5]] = 5 ("ababa")
(0-base)
----
## num 數組
某個state的回文有幾個回文後綴
假設某個 state 代表的回文為 = "ababa" 為例
state 代表的回文的 num = 3
-> ababa -> aba -> a
----
## cnt 數組
某個 state 的回文在整個字串中出現次數
S = "aababaa"
state[3] 代表的回文為 "aba" 在整個字串中出現 2 次
因此
cnt[state[3]] = 2
----
## fail
每個 state 的次長回文後綴的 state 編號
S = "ababa"
len[fail[4]] = 3 (fail[4] = "aba")
len[fail[2]] = 1 (fail[2] = "a")
len[fail[0]] = 0 (fail[0] = "" 空字串)
0 所代表的 state 是空字串
---
今天講得以上演算法複雜度都是 $O(N)$ :D
十分的強大，特別說一下我們的 SA 模板是世界級的
在 CSES 上面跑的速度隨便都可以搶下 Top Coder
CSES 2105 (其中第一名跟第四名都是使用這個模板)
----
KMP 演算法雖然如果怕賽中很容易寫錯可以帶一下模板，
但其中 次長相同前綴後綴 (failure function) 的概念非常重要
很多題目都會在 KMP 上面 DP 因此要好好搞懂
----
迴文的部分大部分只需使用到 manacher 即可(賽中抄模板時相對短)
缺點是他會塞字元 "@" 在每個中間要好好算一下 index
但如果題目需要求較複雜的東西，通常才需要用到
但如果只需要用 manacher 可以解決的問題直接用回文樹的話會非常無腦好寫
各有優缺點
----
Homework
[作業連結](https://vjudge.net/contest/532827)
作業期限到下星期日晚上
由於主要是模板題所以放多一點應付各種題型
Google Drive
Gist
Clipboard
Sign in with Wallet
