字串演算法

進階程式競賽技巧

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"

有了後綴數字，就看哪兩個連續的後綴字串為不同字串相間
然後取 max 即為答案

應用 - 相異子字串數量

給定一個字串 S \(( 1 \le |\)S\(| \le 10^6)\)
求字串 S 中有幾個相異子字串

S = "aabaa"

所有相異子字串為
"a", "b", "aa", "ab", "ba", "aab", "aba", "baa",
"aaba", "abba", "aabaa"

透過 SA 求出 Height 數組

字串 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")為開頭的後綴

即可得到兩後綴的 LCP

用法

模板 SAIS.cpp

傳入參數: ip 陣列放字串，len為字串長度
需保證 ip[len]為 0，且字串裡的元素不為 0

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|) 時間比對字串是否相同

比對第一個字元相同

比對第二個字元相同

比對第三個字元相異

把 W 字串往右一格重新比對，比對失敗

再把 W 字串往右一格重新比對，第一格相同

比對第二格相同

比對第三格相同

比對第四格相同

比對第五格相同

比對第六格相異

再把 W 字串往右一格重新比對，第一格相異

再把 W 字串往右一格重新比對，第一格相異

再把 W 字串往右一格重新比對，第一格相同

第二格相同

第三格相異

再把 W 字串往右一格重新比對，第一格相異

再把 W 字串往右一格重新比對，第一格相同

第二格相同

第三格相同

第四格相同

第五格相同

第六格相同，找到一組解

會發現過程中，有很多不必要的匹配

每次失敗就要重頭開始嘗試匹配

在匹配失敗時，前面已經有一段不用重新匹配
我們只需要從那之後開始匹配即可

從第3個字元開始匹配

再次匹配失敗，把字串移動到必要的匹配上

從第1個字元開始匹配

次長相同前綴後綴

可以知道最長相同前綴後綴是字串自己本身

而我們要求的是次長，以 abcabd 為例

failure function

則當匹配失敗時，取其次長相同前綴後綴，
則可以直接移動詢問字串 W 到還未匹配過的位置

while 還沒比對到最後一個字元:
    if 比對字元成功:
        比對下一個字元
    else if 比對字元失敗:
        取其次長相同前綴後綴，移動字串 W
    else if 成功匹配整個字串:
        紀錄答案，並且取其次長相同前綴後綴，移動字串 W

為了實作方便，
會將儲存次長相同前綴後綴最後一個字元的 index (0-base)

如果為空字串則為 -1，第一個 index 為 0，所以設前一個 0-1 = -1

程式碼

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

建 次長相同前綴後綴表

當一個字串想要加長 次長相同前綴後綴
則需在最尾端加上一個跟前綴下一個字元相同的字元
如果下一個相同代表可以加長，否則需要回到當前的次長相同前綴後綴

abccab \(\to\) abccabc

因此當我們求出前 \(i\) 個字元的次長相同前綴後綴，
如果想要求 \(i+1\) 的次長相同前綴後綴

則是看原本的位置指到字元能不能加長

如果相同則可以加長
否則則找次長相同前綴後綴

程式碼

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

s 為傳入的字串，len為字串長度，z為儲存答案的陣列

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

模板

如模板註解所寫 : 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

裡面重要的有

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

作業連結

作業期限到下星期日晚上
由於主要是模板題所以放多一點應付各種題型