<style> .reveal .slides { text-align: left; font-size:30px } </style> # String Algorithm ---- - Suffix Array - Manacher - Zvalue - MinRotation - Palindromic Tree --- ## Suffix Array ### 後綴數組 簡稱 SA，將字串的所有後綴排序後的數組 ---- 主要有兩個數組：`SA[N]、H[N]` ---- ## SA 數組 把字串的所有後綴排序後的結果 以字串 S = "babd" 為例 所有後綴有 "babd" "abd" "bd" "d" 排序後為 "abd" "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^2\log N)$ 做到 $O(N\log N)$ 排序，$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 ---- ## 用法 [模板 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) } ``` ---- ## 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 --- ## 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`] ---- 馬拉車的程式碼相對較短，並且複雜度為 $O(n)$ 但須好好算奇數偶數的 index 可以在平時沒事就多練習怎麼算，在賽中也會推比較快 --- ## Z value [模板](https://github.com/jakao0907/CompetitiveProgrammingCodebook/blob/master/string/zvalue.cpp) 如模板註解所寫 : z[i] = lcp(s$_{[0:n-1]}$, s$_{[i:n-1]}$) 複雜度 $O( |s| )$ ---- z[i] = lcp(s$_{[0:n-1]}$, s$_{[i:n-1]}$) 丟進去字串 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 ---- ## 例題 --- Genetic Sequence Searching 給定字串 $S$ 和 $T$， 求出 $S$ 中有多少與 $T$ 長度相同的子字串， 跟 $T$ 差最多一個字元 - $1\le |T|, |S|\le 10^6$ ```=txt meowmeowow owo ``` ``` 2 ``` ---- 差最多一個字元等價於， 與 T 的前綴某段長度 x 相同 + 後綴某段長度 y 相同 $\ge$ |T|-1 owo <-> owm = 2 + 0 owo <-> oao = 1 + 1 owo <-> owo = 3 + 3 ---- 求與 T 的前綴某段長度 x 相同，可以使用以下兩種方法 - Hash + Binary Search - Z value 第一個複雜度 $O(n \log n)$ 第二個複雜度 $O(n)$ ---- ### 使用 z value 建表 要出 S 中每個字元開始與 T 的前綴長度有多少相同 直接兩個字串合併丟進去 zvalue(T + '@' + S)，$O(n)$找到每個位置的 LCP 而後綴只需要把字串反過來再重新建一次 zvalue(rev(T) + '@' +rev(S)) 則可以 $O(n)$ 找到反過來的 LCP ，也就是最長共同後綴 ---- 以 S="mowmoao" , T="owo" 舉例 z_value(T + '@' + S): ``` T+@+s = o, w, o, @, m, o, w, m, o, a, o zvalue = 11, 0, 1, 0, 0, 2, 0, 0, 1, 0, 1 ``` z_value(rev(T) + '@' + rev(S) ): ``` rT+@+rS = o, w, o, @, o, a, o, m, w, o, m zvalue = 11, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0 ``` ---- 可以利用長度為 $\vert$T$\vert$ 的滑窗依序檢查 z_value(T + '@' + S): ``` T+@+s = o, w, o, @, m, o, w, m, o, a, o zvalue = 11, 0, 1, 0, 0, 2, 0, 0, 1, 0, 1 滑動視窗 = |_____| ``` z_value(rev(T) + '@' + rev(S) ): ``` rT+@+rS = o, w, o, @, o, a, o, m, w, o, m zvalue = 11, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0 滑動視窗 = |_____| ``` 滑窗代表的區間為 在 S 中，某個長度為 $\vert$T$\vert$ 的子字串 ---- 這時候要判斷這個子字串是不是合法答案 可以看正左界的 z_value 值和反左界的 z_value 值相加是否 $\geq$ $\vert$T$\vert$-1 z_value(T + '@' + S): ``` T+@+s = o, w, o, @, m, o, w, m, o, a, o zvalue = 11, 0, 1, 0, 0, 2, 0, 0, 1, 0, 1 滑動視窗 = |_____| 正左界 = ^ ``` z_value(rev(T) + '@' + rev(S) ): ``` rT+@+rS = o, w, o, @, o, a, o, m, w, o, m zvalue = 11, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0 滑動視窗 = |_____| 反左界 = ^ ``` 在這裡是 $1 + 1\geq$ $\vert$T$\vert$-1 因此 "oao" 是一個合法的答案 ---- z_value(T + '@' + S): ``` T+@+s = o, w, o, @, m, o, w, m, o, a, o zvalue = 11, 0, 1, 0, 0, 2, 0, 0, 1, 0, 1 滑動視窗 = <-|_____| 正左界 = ^ ``` z_value(rev(T) + '@' + rev(S) ): ``` rT+@+rS = o, w, o, @, o, a, o, m, w, o, m zvalue = 11, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0 滑動視窗 = |_____|-> 反左界 = ^ ``` 接著 $O(N)$ 移滑窗，計算當前子字串是否合法 --- ## minRotation ### 最小表示法 求出字典序最小的rotation ---- ### [模板](https://github.com/jakao0907/CompetitiveProgrammingCodebook/blob/master/string/minRotation.cpp) 對於一個長度為 $N$ 字串 $S$ ，找到一個位置 $a$ $(0 \leq a < N)$ 使得 字串 $T=$ $S_{[a..N -1]}+S_{[0..a -1]}$字典序最小 時間複雜度 : $O(N)$ ---- 以 $S$ ="adcab" 為例 : - $a=0$，$T$ ="adcab" - $a=1$，$T$ ="dcaba" - $a=2$，$T$ ="cabad" - $a=3$，$T$ ="abadc" - $a=4$，$T$ ="badca" 當 $a=3$ ， $T$的字典序最小 ---- ## [CSES 1110](https://cses.fi/problemset/task/1110) 把字串丟進去模板裡面，會得到位置 $a$ ```cpp! //rotate(begin(s),begin(s)+minRotation(s),end(s)) int minRotation(string s) { int a = 0, N = s.size(); s += s; rep(b,0,N) rep(k,0,N) { if(a+k == b || s[a+k] < s[b+k]) {b += max(0, k-1); break;} if(s[a+k] > s[b+k]) {a = b; break;} } return a; } ``` 第一行註解可以直接讓一個字串做 rotate ，得到字典序最小的 rotation --- ## 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[state[4]]] = 3 (fail[state[4]] = "aba") len[fail[state[2]]] = 1 (fail[state[2]] = "a") len[fail[state[0]]] = 0 (fail[state[0]] = "" 空字串) 0 所代表的 state 是空字串 --- 今天講得以上演算法複雜度都是 $O(N)$ :D 十分的強大，特別說一下我們的 SA 模板是世界級的 在 CSES 上面跑的速度隨便都可以搶下 Top Coder CSES 2105 (其中第一名跟第四名都是使用這個模板)~~(一年前QQ)~~  ---- 今天講的模板應該都算簡單好懂，而 SA 的變化相對較多較難 可以多練題目熟悉 而 90% 的字串問題使用以往&今天教過的內容都是能解決的 因此好好熟練 CP 值很高 CSES 上的 String 題單應該也能解掉大部分 ---- 迴文的部分大部分只需使用到 manacher 即可(賽中抄模板時相對短) 缺點是他會塞字元 "@" 在每個中間要好好算一下 index 但如果題目需要求較複雜的東西，通常才需要用到 ~~但用 manacher 可以解決的問題砸回文樹的話會非常無腦好寫~~ 各有優缺點