字串演算法 (String)

這個暑假看了動態規劃(1),(2)，線段樹、最短路徑、計算幾何、字串演算法，這一篇的完成算是暑假的一個里程吧！接下來繼續學習不同的主題，再把筆記更新到部落格中！

課程內容

字串

定義
- 大寫 $\Sigma$ 表示字元集
- 字串：有限個字元集組成
- $|\Sigma|$ 字元集大小、|S|字串長度
- S[a:b]表示連續從字元a到b
子字串：S[a:b]
前綴：S[0:b]
後綴：S[a:|S|-1]

字典樹Trie

定義
- 例題：字串出現次數
- 一顆由根、邊一綠往下指的有向樹
- 每個邊為字元、每一點代表字串
- 每經過一條邊，字串加上邊的字元
- 根節點為空字串！
操作
- 查詢字串：$O(L)$，由根順著邊往下找
- 插入字串：$O(L)$，不斷往下走直到空節點，在Trie加入一個節點
- 節點必須記錄當前是否為有效字串
- Trie結構中包含：字串、紀錄字串出現次數

KMP

功能：進行字串匹配
例題：字串S在字串T哪些位置出現
- 暴力匹配：時間 $O(|S|\times|T|)$
F[i]表示當配對成功A[0:i]後即配對失敗，將A[F[i]]對齊原本A[i]的位置
搭配F[i]調整在串移動的長度
匹配：複雜度 $O(|T|)$，建立F函數：$O(|S|)$

漢明距離(Hamming distance)

兩個等長字符串對應位置的不同字符的個數

Z-value

z[i] 是指由 s[i] 開始的字串，與 s[0] 開始的字串可以匹配到多長
S[0:k-1] = S[i:i+k-1]
z[0] = 0

Rolling Hash

之前隨機講過

後綴數組（Suffix Array）

將一個字串的所有後綴進行排序
基數排序（Radix Sort）

最長共同前綴（LCP,Longest Common Prefix）

兩字串的最長共同前綴
將最長共同前綴轉換成區間最小值問題

字串演算法主題

字典樹Trie

字典樹是以指標型態建立的一棵樹，邊代表一個字元、節點代表從根一路走來的邊形成的字串，從根節點開始（根節點為空），每經過一條邊，就把字串加上那一條邊對應的字元，直到找出要匹配的字串。如果有多筆獨立的詢問，只要加上Delete函數就可以了！

Trie結構

實作上的陣列c指向個別的字元，不一定要用cnt，根據題目的所求調整不同的變數設定。

struct Trie{        //利用指標建立一棵樹
    Trie* c[26];    //對應a-z每一條邊
    int cnt;        //字串出現次數
    Trie(): cnt(0){ //初始設定
        memset(c,0,sizeof(c));
    }
};
Trie* root;

Insert函數

在插入的過程中言錄新增路徑，一樣嘢可以根據題目要求在過程中進行變數紀錄等。如NEOJ 267 自動完成系統。

void insert(char *s){
    Trie *ptr = root;           //從根節點尋找
    while(*s){
        if(!ptr->c[ch(*s)])     //如果樹上無此字元則new
            ptr->c[ch(*s)] = new Trie();
        ptr = ptr->c[ch(*s)];   //繼續造訪Trie
        s += 1;                 //字串下一個字元
    }
    ptr->cnt += 1;              //字串出現次數(字串對應唯一葉節點)
}

查詢函數

一個字串對應到唯一的路徑，從根節點根據每一個字元決定路徑。

int find(char *s){              //查找字串s
    Trie *ptr = root;           //根節點尋找
    while(*s){                  //無此字串，回傳次數0
        if(!ptr->c[ch(*s)])return 0;
        ptr = ptr->c[ch(*s)];
        s += 1;                 //字串下一個字元
    }
    return ptr->cnt;            //回傳字串出現次數
}

Delete函數

void clear(Trie *s){
    for(int i=0;i<26;i++){
        if(s->c[i]){
            clear(s->c[i]);
            delete s->c[i];
            s->c[i] = nullptr;    //很重要
        }
    }
}

KMP Algorithm

首先要求出Failure Function，它可以在 $O(|S|)$ 建立。失敗函數的定義是：

$F[i]$ 表示當成功配對 $A[0:i]$ 之後，配對失敗時，我們會將 $A[ F[i]]$ 對齊原本 $A[i]$ 的位置

如果寫成數學式的定義：

$F_A(J)=\left\{ \begin{array}{l} -1,&&\text{if j = 0}\\ max\{p:A_{0...p} = A_{j-p...j} \text{ and 0≤p<j}\},&&\text{otherwise}\\ \end{array} \right.$

這個函式以中文來說就是「最大前綴後綴」！

這個函數可以讓我們知道，當配對在較短字串 $S$ 在第 $i$ 位配對失敗時，要找到第 $F[i]$ 去繼續比對。從比較直觀的角度去理解，就是把字串要往右移幾格才能正確匹配上，如果配對失敗，則尋找更前面更短的子字串試試看。

以比較數學的角度看到底要怎麼建立Failure Function，可以從以下推導得知：

假設 $F[i] = x, x≠-1$，根據上面的定義有這樣的等式：$A[0:x] = A[i-x:i]$
分成以下兩種情況做討論：

$A[x+1] = A[i+1]$
這種情況就是兩邊的下一個字串都相同，直接將繼承前面的長度為x的子字串，因此有關係式$F[i+1] = x+1$
$A[x+1] ≠ A[i+1]$
這種情況比較棘手，我們無法繼續使用之前長度為x的子字串，因此我們要尋找前面更短的字串進行匹配。假設我們找到 $K$ 滿足 k<x，同時 $A[0:k] = A[i-k:i]$ ，這時候我們只需確認 $A[k+1]=A[i+1]$ 是否成立即可，如果不成立則繼續尋找比 $K$ 更短的子字串。

從剛剛的關係式，我們可以繼續寫下去： $A[0:k] = A[i-k:i]=A[x-k:x]$，理由是i的後綴與x後綴相同，因此 k的後綴就會和x的後綴相同。由失敗函式的定義推斷，我們要找的 $k$ 就會是 x 的失敗函式，$K = F[x]$。

如果找到的k不滿足 $A[k+1]=A[i+1]$ ，則會繼續尋找下一個更小的 $k$ 值直到滿足條件或是 $k=-1$ 為止。

再來則是KMP MATCH，能在時間複雜度 $O(|T|)$ 內將匹配出來的位置找出來。具體的方法與建立Failure Function 相近，如果 $A[p+1]≠A[i+1]$，則尋找更小的字串長度 $k<F[i]$ 看能否繼續匹配。當匹配成功，記得把p設為F[p]，因為匹配完成其實也可以看作是下一個字元匹配失敗（$S$ 的空字元對上 $T$ 的下一個）。

至於時間複雜度的部分，分析一下while迴圈總共會執行的次數，當每執行一次，p的值一定會遞減，而p只會在每一個迴圈最多加上一，因此p的增加會是字串長度 $|T|$ 的常數倍，使總複雜度為 $O(|T|)$。

Build Function

//O(|S|)要配對的字串以及Fail Function
void KMP_build(char *S,int *F){
    int p = F[0] = -1;              //初始設定為-1
    for(int i=1;S[i];i++){          //1到接下來字元
        while(p!=-1 && S[p+1]!=S[i])
            p = F[p];               //無法繼續配對，尋找更短字串
        if(S[p+1] == S[i])          //配對成功(如都沒有一樣的就-1)
            p += 1;
        F[i] = p;                   //設定F[i]
    }
}

Match Function

vector<int> KMP_match(char *S,int *F,char *T){
    vector<int> ans;            //回傳匹配相同地方
    int p = -1;                 //紀錄短字串有多少被匹配
    for(int i=0;T[i];i++){      //每一迴圈都讓T[i]被匹配到
        while(p!=-1 && S[p+1]!=T[i])
            p = F[p];           //使T[i]一定可以被匹配到
        if(S[p+1] == T[i])
            p += 1;             //T的第i個與S的p+1可以匹配
        if(!S[p+1]){            //S[p]已經匹配完成
            ans.push_back(i-p); //回推匹配開頭
            p = F[p];           //繼續下一輪匹配
        }
    }
    return ans;
}

Hash (Robin-Karp Algorithm)

雜湊算法的核心概念就是以下公式，可以透過它進行字串比對等等。

$H(s[1:n]) = \sum_{i=0}^n S_i\times C^{n-i}$

詳細內容可以參閱這一篇：隨機演算法

Z Algorithm (Gusfield’s Algorithm)

Z函數的定義是對於字串長度 $n$ 的字串 $S$ ，$z[i]$ 函數代表 $S[0:n-1]$ 和 $S[i:n-1]$ 的最長共同前綴，也就是LCP長度。定義 $z[0] = 0$。

有講義上面寫Z Function很簡單，但我覺得有夠難，難度跟KMP的理解差不多。根據Z函數的定義，我們可以$O(N^2)$建立z函數，顯然時間有些太多了。如果我們算 $Z[i]$ 的值可以用 $Z[0:i-1]$ 轉移過來，會省下許多時間，把時間降成 $O(N)$。

算法概念

整個算法的核心概念就是利用前面已經算好的Z Function去推現在的值，有點像動態規劃的概念。在整個過程中我們會維護右端點最大的匹配段（與前綴匹配），其表示為 $[l:l+Z[l]]$，也可以寫作 $[l:r]$，保證 $l ≤ r$。在計算 $Z[i]$ 的過程中，分別討論以下三種情形：

$i ≤ r$
根據定義，因為區間 $[l:r]$ 本身是前綴，因此當 $i$ 在區間中間時會將區間分成左右兩半邊，將正個區間往前平移會讓 $i$ 對應到 $i-l$ 的位置，又此時區間為 $[0:r-l]$ ，因此$z[i] = min(z[i-l],r-i)$。
- $z[i-l] ≤ r-i$
  已經知道 $z[i-l] < r-i$ 表示在前後兩區間（分別從0,i開始）在一樣的情況下做多不超過 $z[i-l]$ 長度的匹配，因此第 $z[i-l]$ 的下一個字元必定無法繼續匹配成前綴。
- $z[i-l] > r-i$
  在這種情況下已知 $s[0:r-l] = s[l:r]$，根據定義 $s[i-l:r-l] = s[i:r]$。因為 $z[i-l] > r-i$，$z[i-l]$ 右端的範圍會超過 $r$ ，也就是說超過 $r$ 之後這個性質 $s[i-l:r-l] = s[i:r]$ 就不會成立，但可以確定 $z[i]$ 至少為 $r-i$。接著就暴力枚舉即可！

上面的內容可以用下圖解釋，兩條紅線段是一樣的，$x=i-l$ ，接著討論$Z[x]$ 的長度就可以知道該如何更新。

$i > r$
這種情況我們可以直接暴力跟前綴匹配。

程式實作1

程式碼中 $bst$ 表示的是左界 $l$，右界則是 $bst+Z[bst]$。

void Z_algo1(char *S,int *Z){
    int bst = 0;                            //相當於左界，大小為z[bst]
    Z[0] = 0;
    for(int i=1;S[i];i++){
        if(Z[bst]+bst < i)Z[i] = 0;         //直接暴力枚舉
        else Z[i] = min(Z[i-bst],bst+Z[bst]-i);
        while(S[Z[i]]==S[i+Z[i]])Z[i]++;    //依序暴力枚舉
        if(Z[i]+i > bst+Z[bst])bst = i;     //更新更遠的右界
    }
}

程式實作2

這個實作超級短，沒有幾行就解決了，但他的效果卻是一樣的！

void Z_algo2(char *S,int *Z){
    int l = 0, r = 0;                       //左右界
    Z[0] = 0;
    for(int i=1;S[i];i++){
        Z[i] = max(min(Z[i-l],r-i),0);
        while(S[i+Z[i]] && S[Z[i]] == S[i+Z[i]]){
            r = i+Z[i];               //更新右界
            Z[i]++;
        }//保證當Z[i]從Z[i-l]轉移時不會被更新！
    }
}

時間複雜度

根據以上兩個程式碼可以發現，右界 $r$ 或是 $bst+Z[bst]$ 在過程中是不斷增大的，且r必定不會超過n，因此迴圈跑下來複雜度會是 $O(N)$。

LPS (Manacher’s Algorithm)

LPS (Longest Palindromic Substring)就是最長回文子字串，Naive的作法是每次 $O(n)$ 向兩側擴展，時間是 $O(n^2)$。

Manacher’s Algorithm這個演算法的概念和Z Alogorithm相近，可以在 $O(n)$ 的時間內找出以每一個點為中心之最長回文長度。回文的定義是無論從正序或是逆序看一個字串都是一樣的，分為兩種：一種是奇數的對稱，也就是以一個字元為對稱中心往兩側擴展；另一種則是以字元間的空格為對稱中心向兩側對稱。

這兩個的性質很不同，在處理的時候我們也不知道到底是呈現怎麼樣對稱的狀況，因此可以使用一種手法：將每一個字元中間插入同樣沒有出現過的字元，如此一來不論是偶數或是奇數長度的字串，在加入這個沒有出現過的字元之後，都會變成奇數長度的回文了！

定義 $z[i]$ 為以 $s[i]$ 為中心，最長的回文長度LPS（如果字元i是自己回文，定義Z[i] = 0]）。以字串abba來說就是以下情況：

編號	1	2	3	4	5	6	7	8	9
原字串	a	b	b	a
變更後	.	a	.	b	.	b	.	a	.
Z函數	1	2	1	2	5	2	1	2	1

跟Z Alogrithm 一樣，維護一個右界最遠的區間 $[l,r]$，作為在算 $z[i]$ 時能使用到的 $z[0:i-1]$ 的最大值，令他為 $r$。取j滿足 $j+z[j]$ 有最大值，分成以下兩個條件做討論：

1. r < i
這種情況就表示不能用之前算的東西去更新現在的值，因此只能暴力枚舉 $s[i]$ 的左右兩側，看最長回文的長度為何。

2. r > i
分成三種情況討論（比z algorithm多了一個），首先因為 $r > i$，右界覆蓋了 $i$，表示我們可以從 $j$ 的另外一端映射出與 $s[i]$ 相同的 $s[i’]$（以 $j$ 為中心回文呈現兩側對稱），映射的索引值為 $2j-i$，如下圖：

因為 $z[i’]$ 已經計算過了，因此可以將 $r-i$ 以及 $z[i’]$ 的大小分成三種情況討論：

$z[i’] < r-i$
這種情況表示 $z[i’]$ 無法繼續往右邊更新，因為 $i$ 與 $i’$ 都是在以 $j$ 為中心的回文中，兩邊是一樣的，代表 $z[i] = z[i’]$ 且不可能再被更新成更大的範圍。
$z[i’] = r-i$
這種情況下是要枚舉的，從兩側映射的關係知道 $z[i]$ 的長度至少為 $r-i-1$，因此將 $z[i]$ 設為 $r-i$ 繼續枚舉就可以了！
$z[i’] > r-i$
由下圖觀察發現，$z[i]$ 不可能比 $r-i$ 還要大，直接將值設為 $r-i$ 即可。

時間複雜度

觀察到while迴圈執行的狀況，只有當 $r < i$ 以及 $z[i’] = r-i$ 時右界才有被更新的可能，兩種情況都會讓右界 $r$ 遞增，範圍最大到 $n$ ，因為不會減小的關係，總時間複雜度為線性的 $O(n)$！

程式碼

void Longest(){
    n = strlen(T);m = 2*n+1;
    memset(S,'.',m);
    for(int i=0;i<n;i++)S[2*i+1] = T[i];    //間隔插入沒出現過字元
    Z[0] = 1;                               //計算時使用右開區間
    int l = 0,r = 0;                        //維護最大右界左右界
    for(int i=1;i<m;i++){
        Z[i] = max(min(Z[2*l-i],r-i),1);
        while(i-Z[i]>=0 && i+Z[i] < m && S[i+Z[i]]==S[i-Z[i]]){
            l = i;r = i+Z[i];
            Z[i]++;
        }
    }
}

後綴數組

一些基本定義，我們定義 $suf[i]$ 是字串 $S$ 從 $i$ 開始的後綴，也就是 $S[i:n-1]$。將一個字串所有的後綴取出來按照字典序進行排序，就是後綴數組。總共有三個複雜度：$O(n^2\log n)$、$O(n\log^2 n)$、$O(n\log n)$ 分別是使用暴力、倍增、基數排序的優化。

暴力解 $O(N^2\log n)$

$O(n)$ 的字串比對，排序 $O(n\log n)$，因此時間複雜度為 $O(n^2\log n)$。

int n,m;
char S[10] = "algorithm";

bool cmp(int a,int b){
    return strcmp(S+a,S+b) < 0;
}

int main(){
    int SA[10];
    n = strlen(S);
    rep(i,0,n-1)SA[i] = i;
    sort(SA,SA+n,cmp);
    rep(i,0,n-1)cout<<SA[i]<<" ";
    cout<<endl;
}

倍增+Quick Sort

使用倍增可以讓複雜度做到 $O(n\log^2 n)$，其原理主要是讓比較的時間併入排序，同時多做 $O(\log n)$ 層的排序。定義 $sa[i]$ 為將後綴排序後第 $i$ 小的後綴編號；$rk[i]$ 表示後綴 $i$ 的排名。

倍增顧名思義，跟將數量乘上兩倍有關，因此會帶一個log。下圖就是一個排序的示例，首先按這字典序初始每一個字元的排名 $rk[i]$，進行 $O(\log n)$ 層，每一層用 $O(n\log n)$ 的時間進行排序。倍增讓原本的字串比較 $O(n)$ 降到 $O(\log n)$ 。

接下來的每一層的每一個字元 $s[i]$，在比較大小的時候，將 $rk[i]$ 以及 $rk[i+k]$ 組成一個 $pair$ 進行排序，從第一層開始，每一層的 $k$ 都會增加為2倍（倍增的概念）。pair的first就好比倍增時前 $s[i:i+k]$ 的排名、second就是 $s[i+k+1:i+2k]$ 的排名，搭配字典序是按照由前到後進行排名，比完fisrt才會比second，如此一來我們可以利用倍增的性質，也就是已經排名好的較短長度的字串，直接利用排好的名次進行下一輪的排序，這就導致我們不需要對每一個字元都看過一遍！

圖片出處圖中的黑線岔開距離都會因為每一層而越岔越開（乘上2倍），也就是「倍增」所代表的意義！

void suffix_array(string S){
    n = S.size();
    int lg = 32-__builtin_clz(n);//回傳第一個1之前0的個數（二進位）
    vector<pt> cur(n,{0,0,0});
    vector<int> rk(n+1,-1);
    rep(i,0,n-1)cur[i] = {S[i],0,i};
    rep(p,0,lg){                //進行O(lgn)次
        int k = 1 << p;         //現在倍增的大小
        sort(all(cur),cmp);
        rk[cur[0].id] = 0;
        rep(i,1,n-1)            //設定rk，與前一個相同則設定跟前一個一樣
            rk[cur[i].id] = (cur[i-1]==cur[i] ? rk[cur[i-1].id]:i);
        rep(i,0,n-1)            //倍增pair的second
            cur[i] = {rk[i],rk[min(n,i+k)],i};
    }
    sort(all(cur),cmp);
    rep(i,0,n-1)sa[i] = cur[i].id;
}

搭配 Radix Sort

基數排序 (Raddix sort) 以及計數排序 (Counting sort) 兩者是有點從屬的關係，計數排序是基數排序的子程序，也就是說基數排序是透過對每一位進行計數排序完成的！

首先，我們需要 $O(n)$ 的空間進行每一輪的計數排序，對每一個元素進行排名（從1到n-1），如此一來才能確保不會有溢位的問題。先對第二個關鍵字進行排序，排完之後再按照第一個關鍵字排序。Raddix Sort 是穩定的，相同元素為在前面在排序之後一定會在前面。

有幾個地方有實作上進行基數排序的限制，首先第一輪會按照個別字母的字典序進行排序，用快排等基於比較的排序方法可以順利完成，但可惜基數排序不行，一定要乖乖的按照 1 到 n-1 順序進行排名。因此在第一輪會先使用 $std::sort$ 排名，之後進行raddix_sort！

最後一個小小的地方，就是當第二個 key 的值為 -1的情況（倍增超出範圍），在比較時可以直接push進去答案裡面，因為並沒有一個box的index 是-1，同時他們也是最小，丟進去即可。

時間複雜度： 每一層進行 $O(n)$ 排序，因為倍增共有 $O(\log n)$ 層，因此總時間複雜度為 $O(n)\times O(\log n) = O(n\log n)$！

void raddix_sort(vector<pt> &cur){
    init();
    rep(i,0,n-1){
        if(cur[i].y == -1)temp.push_back(cur[i]);
        else box[cur[i].y].push_back(cur[i]);
    }
    rep(i,0,n-1)
        for(auto j : box[i])temp.push_back(j);
    rep(i,0,n-1)box[i].clear();
    rep(i,0,n-1)
        box[temp[i].x].push_back(temp[i]);
    cur.clear();
    rep(i,0,n-1)
        for(auto j : box[i])cur.push_back(j);
}

最長共同前綴 LCP (Kasai’s Algorithm)

最長共同前綴，以現在字串演算法中，假設 $lcp(i,j)$ 為後綴 $i$ 與 $j$ 的最長共同前綴。在這篇文章中給出這個定義：

A value lcp[i] indicates length of the longest common prefix of the suffixes inexed by suffix[i] and suffix[i+1]

定義 $lcp[i]$ 為後綴 $i$ 與後綴 $i+1$ 的最長共同前綴，其中 $lcp[n-1]$ 沒有定義。再複習一下，$rk[i]$ 為第 $i$ 個後綴數組的排名$rk[i]$、$sa[i]$ 為排名為 $i$ 的字串所對應到的從 $sa[i]$ 開始的後綴數組。

到底我們要求的LCP是什麼？如果只是給兩個字串要求出共同最長前綴，那我們只要 $O(min(L_A,L_B))$ 就好，是可以接受的複雜度。但Kasai’s Algorithm不是要求這個。一般都在講到後綴字串之後講到LCP，為的就是要求出所有的後綴數組中，任兩個字串的共同最長前綴為何。以一個字串長度為 $l$ 來說，後綴的配對數量共有 $O(l^2)$ 組，暴力肯定會TLE。

求出 $lcs$ 需要有兩個引理：

第一個引理 $lcp[rk[i]] ≥ lcp[rk[i-1]]-1$ 其中 $i$ 為尚未經過排序的從 $i$ 開始的後綴字串。

說明： 將後綴數組排序之後有點像將相似的字串排在一起（按字典序由小排到大），鄰近的字串其實代表著一個意義，兩者相似程度越高。因此 $lcp[rk[i-1]]$ 某種意義代表著與 $i-1$ 開始的後綴數組（簡稱後綴 $i-1$）跟其他字串最大的共同前綴長度。

接著我們看 $lcp[rk[i]]$ ，後綴 $i$ 就是後綴 $i-1$ 刪掉一個前綴字元的結果。我們假設跟後綴 $i-1$ 相近的那個字串叫做 $T$ （其實就是後綴 $rk[i-1]+1$），把 $T$ 刪除一個前綴字元之後所形成的字串（也就是比 $T$ 再短一字元的後綴）也就可以跟後綴 $i$ 進行匹配，其長度因為被刪掉一個前綴字元所以少一，因此得到了以上式子。

聽說很難證明，不過至少可以情感上的接受這件事是對的！

第二個引理 $lcp(S_i,S-j) = min_{i≤k<j}(S_k,S_{k+1})$

為什麼可以算出最近的排名的LCP即可得到最長的LCP？從這個定理可以看出來，對於後綴 $i$ 以及後綴 $j$ ，取 $min$ 的原因是要確保所有的中間後綴 $k$ 都包含了下界 $k$ ，也就是說每個在 $i$ 與 $j$ 中間的人都至少跟前一個人相同個字元。

以下以字串 $aabaabc$ 作為範例：

後綴	RK	String
0	0	aabaabc
1	2	abaabc
2	4	baabc
3	1	aabc
4	3	abc
5	5	bc
6	6	c

以下是SA與對應的String

RK	SA	String	LCP
0	0	aabaabc	3
1	3	aabc	1
2	1	abaabc	2
3	4	abc	0
4	2	baabc	1
5	5	bc	0
6	6	c	0

以下是找LCP流程：

首先從後綴0開始，找到對應的下一個rk，也就是後綴3，得到LCP為3
接下來看後綴1，查表得到RK為2，找到RK為3的找LCP，得到2
看後綴2，與RK為4,5名找LCA，得到1
後綴3，看RK 1,2，LCA為1
接下來以此推累

接下來有兩種不同設定方法，端看要採用的是上表還是下表的字串排序方法。我以上表為例，程式執行時印出順序：$3211000$；也可以採用後綴數組排序後的結果（一般都採用此方法），直接對應出順序（對照的是下表）：$3120100$。

vector<int> LCP(string s){
    vector<int> rk(n,0),lcp(n,0);
    rep(i,0,n-1)rk[sa[i]] = i;      //利用sa反函數得到rk
    int k = 0;
    rep(i,0,n-1){
        if(k)k--;
        if(rk[i] == n-1)continue;   //rk[n-1]未定義
        int j = sa[rk[i]+1];        //下一名後綴從何開始
        while(i+k<n && j+k<n && s[i+k] == s[j+k])k++;
        lcp[rk[i]] = k;
    }
    return lcp;
}

時間複雜度： 主要觀察 $k$ 的變化，$k$ 最多就是n，最少是0，最差的情況是 $k$ 被減掉 $n$ 次，加上 $2n$ 次，因此複雜度是線性 $O(n)$！