[ Cyclic Longest Common Subsequence ] 環狀最長共同子序列

相信會看我發的文的人應該多少都知道LCS(最長共同子序列)是什麼吧？對於這樣的問題很早以前就有人提出$\ord{nm}$的方法了。
現在如果將問題中的字串改成頭尾相接環狀的字串，我們稱其最長共同子序列為CLCS，例如：

設A,B為頭尾相接環狀字串

A = "aabaa" , B = "aaabb"

CLCS(A,B) = "aaab"

像這樣的問題要怎麼解呢？剛好codeforces上面就有一題：http://codeforces.com/gym/100203/problem/B

為了解決這一題，查閱了不少奇怪的文章，最後給我找到了這篇論文：Solving Cyclic Longest Common Subsequence in Quadratic Time

對於CLCS提出了$\ord{nm}$的演算法，在這裡附上該演算法的實作：

作法大致上是將b字串變成原來的兩倍，然後做一般的LCS，但在過程中要注意更新答案的順序。接著修改DP來源表格，每次將來源表格的第一個row刪掉(reRoot函數)，然後計算當前的答案。

當我AC這一題後，我看到了一個非常驚人的作法，也是用DP複雜度是$\ord{nm}$，但是我目前還無法完全理解為何這樣是可行的，而且這樣的做法我也不知道如何回溯找出一組解，只能知道CLCS的長度，希望路過的大大們能提供想法：

[ Earley parser ] Earley語法解析器

有一天蚯蚓跟我說CYK算法很慢，推薦了這個東西，所以我就把他寫出來了。
他主要是先建構出類似於自動機的圖，有很多個狀態在跳來跳去，在我的實作裡有將其轉成語法樹的方法。
這裡需要自己實作的有lexer，還有最後的語法一定要有一個gamma rule，gamma rule就是有一個$gamma \Longrightarrow S$，$S$是初始符號。
首先是語法規則的部分:

這是分析器的本體，lexer的部分要自己去完成，lexer的結果會是parse的第二個參數，計算出來一些資料會存在table裡面
以下為模板:

最後是構造語法樹的部分，因為div是一顆左兄弟右兒子的樹，所以要將她轉換成正常的語法樹，還要去記錄曖昧文法的部分:

[ Rabin-Karp rolling hash ] Rabin-Karp 字串hash演算法

Michael O. Rabin和Richard M. Karp在1987年提出一個想法，即可以對模式串進行哈希運算並將其哈希值與文本中子串的哈希值進行比對。
設字串陣列為\(S[n]\)，字元編號為\(0\)到\(n-1\)
首先建立陣列\(Hash[n+1]\)，\(Hash[i]\)表示
\((S[0]*P^{i-1}+S[1]*P^{i-2}+...+S[i-1])\%PM,Hash[0]=0\),其中\(P\)跟\(PM\)是質數
假設要取編號\(L\)到編號\(R\)左閉右開區間的hash值，則其為\((Hash[R]-Hash[L]*P^{R-L})\%PM\)
如果要用double hash則用不同質數計算兩種不同的hash值，用pair拼起來即可
以下提供模板:

[ Palindromic Tree ] 回文樹(回文自動機)

回文樹是去年新出的資料結構，由一個俄羅斯codeforces的紅人Mikhail Rubinchik在2014年發明的(http://codeforces.com/blog/entry/13959)，雖然名子直接翻譯叫回文樹，但他長的比較像一個自動機，所以也有很多人翻回文自動機。
在構造它之前，我們必須先證明一個長度n的字串其不同的回文子字串個數<=n，什麼是不同的回文子字串?就是長的不同的回文子字串，及把出現位置不同但形狀一樣的回文子字串當做是同樣的子字串。

證明:

1. 由左往右一個一個增加字符，則新產生的回文子字串其結尾一定是當前增加的字符x
2. 考慮以當前位置為結尾的最長回文x......x，顯而易見的，若產生除了x......x之外其它的回文子串，則必定被x......x所包含
3. 若增加字符x後，產生了除了x......x之外其它的回文子串，則根據回文的性質，其一定早已在x......的部分理出現(例:假設S是對稱點x...S.xax，因為回文的性質所以S的另一邊也會出現相同的字串xax.S.xax)
4. 因此每增加一個字符最多只會產生一個新的回文子字串，而長度為n的字符串最多只會產生n種不同的回文子字串

接下來進行回文自動機元素的詳細解說:

回文自動機包含以下元素:

1. 狀態St，所有節點的集合，一開始兩個節點，0表示偶數長度串的根和1表示奇數長度串的根
2. last 新增加一個字符後所形成的最長回文串的節點編號
3. s 當前的字符串(一開始設s[0]=-1(可以是任意一個在串S中不會出現的字符))
4. n 表示添加的字符個數

每個節點代表一個不同的回文子字串，我們在每個節點會儲存一些數值:

1. len 表示所代表的回文子字串長度
2. next[c] 表示所代表的回文子字串在頭尾各增加一個字符c後的回文字串其節點編號
3. fail 表示所代表的回文子字串不包括本身的最長後綴回文子串的節點編號
4. cnt(非必要) 表示所代表的回文子字串在整體字串出現的次數(在建構完成後呼叫count()才能計算)
5. num(非必要) 表示所代表的回文子字串其後綴為回文字串的個數

注意一開始必須先將狀態初始化St[0].len=0，St[1].len=-1，last=0，s[0]=-1，n=0

關於構造方法及圖片說明請參考:http://blog.csdn.net/u013368721/article/details/42100363
概念請參考:http://blog.csdn.net/MaticsL/article/details/43651169
證明請參考:http://yqcmmd.com/index.php/2015/03/30/746/

最後提供模板(使用STL vector)，因為St的元素在解題的過程中常會被用到所以就不封裝了:

[ Suffix Array Longest Common Prefix (LCP) ] 後綴數組之最長共同前綴(高度數組)

不解釋了，可以在\(\ord N \)時間內得到，N是字串長度
以下提供模板:

[ Suffix Array SA-IS Algorithm ] 後綴數組線性SA-IS算法

SA-IS是我目前看過最快的線性後綴數組演算法，但是做為競賽用途而進行簡化後他的效率在某些硬體上會比DC3慢，不過記憶體使用量是DC3的1/3~1/2倍，而最短的實現code也比DC3短很多，因此我認為這是十分優秀的算法

因為某些SA-IS的實作方式會利用傳入的陣列s的空間進行計算，因此傳入的陣列s必須是int範圍，而傳入的字串的尾端字元必須是最小的而且在之前完全沒有出現過，因此必須給字串先做以下處理:

假設要傳入字串 mississippi
先在尾端加入字元'#': mississippi#
算法結束後陣列sa為:11 10 7 4 1 0 9 8 6 3 5 2
將第一個數字11去除後剩下的數字即為字串mississippi的後綴數組:
10 7 4 1 0 9 8 6 3 5 2
關於SA-IS算法的論文請看這裡:
Two Efficient Algorithms for Linear Time Suffix Array Construction

關於SA-IS算法的教學(專利申請文)請看這裡:
后缀数组构造方法  CN 102081673 A

SA-IS的教學投影片:
https://www.cs.helsinki.fi/u/tpkarkka/opetus/11s/spa/lecture11.pdf

SA-IS中文教學:
https://riteme.github.io/blog/2016-6-19/sais.html

如果想對Suffix Array算法進行測試請使用這個Online Judge:
http://www.spoj.com/problems/SARRAY/

以下將會提供一些SA-IS的實做模板

1.台大黑暗code界的黑暗codebook:
其實這段code本來是被壓縮得更短，而且用到非常多的記憶體，不過經過卦長的改良後成功減少記憶體的使用並將他排版成正常人能看得懂的樣子
而這裡的MXN則是字串的最長長度(假設字元數<字串長度)

2.卦長自行實作的模板(記憶體用量少):
為了簡化實作方法及減少記憶體的使用，因此將計算後剩下的空間進行重複利用，壓縮後只需要這些記憶空間，而傳入的陣列s可以直接傳入char陣列，因此對使用者來說是非常方便的一份code
這裡的MXN則是字串的最長長度(假設字元數<字串長度)

3.論文提供的實作code:
這是其中一個比DC3快的code，而且記憶體使用量是最少的，但是長度很長就是了，不適合在比賽時使用

4.超快記憶體使用超少的模板庫code:
https://gist.github.com/jacky860226/1d33adad858eef71bfe18120d8d69e6d#file-sa-is-very-fast-cpp
因為長度太長所以就直接貼上網址了，沒有人會在比賽時寫這種東西

[ Difference Cover modulo 3, DC3 ] 後綴數組線性DC3演算法

DC3 是歷史上第一個線性時間的後綴數組演算法，而且相對於 SA-IS 來說更容易作為教材。

這是 DC3 的原始論文：
https://www.cs.helsinki.fi/u/tpkarkka/publications/jacm05-revised.pdf

首先是後綴分類。我們會將所有後綴根據其起始位置 $i$ 對 3 的餘數進行分類，形成三種不同的類型：

• Type A ($i$%3=0):
  這類後綴的起始位置是 3 的倍數。它們不會直接參與初始排序，而是透過 Type B 的排序結果間接排序。
• Type B1 ($i$%3=1):
  這類後綴會與 Type B2 一起組成 Type B 後綴集合，並進行初步排序。
• Type B2 ($i$%3=2):
  同樣屬於 Type B 後綴集合，與 B1 一起進行排序。

以 "mississkp" 為例，為了方便操作我們在其尾端加入兩個哨兵字元 '\0'。

如圖1 所示，首先我們對於每個 Type B 後綴，我們取出其前三個字元作為排序鍵值，將這些三元組視為新的字元（透過 radix sort 將三元組映射為整數，實作上呼叫了三次 counting sort），並對它們進行排序。若排序後的鍵值唯一，則排序完成；否則需將這些鍵值壓縮成新的字母表，並遞迴呼叫 DC3 來排序這個縮小版的問題。

圖1

如圖2 所示，此時 Type B 後綴的排名已經確定了。對於每個 Type A 後綴 i，我們無法直接比較整個後綴（因為效率問題），但可以利用 Type B 的排名來構造一個排序鍵值：

• 對於每個 Type A 後綴 i，我們取：

• $S[i]$：當前字元
• $R[i+1]$：Type B1 後綴的排名（因為 i+1 % 3 = 1）

一次 counting sort 後，我們得到了  Type A 後綴的排名。

圖2

接著我們要合併兩種後綴的排序結果，可以使用 std::merge 合併，但須要寫一個 $\ord{1}$ 的比較函數。設比較函數 $cmp(x,y)$， $x$ 是某個 Type B 後綴的編號，$y$ 是某個 Type A 後綴的編號：

1. $S[x]\ne S[y]$：
   直接比較 $S[x],\;S[y]$
2. Type B1 後綴 ($x$ % 3 = 1)：
   此時 $x+1$ 和 $y+1$ 都是 Type B 後綴，直接比較 $R[x+1],\;R[y+1]$
3. Type B2 後綴 ($x$ % 3 = 2)：
   此時 $x+1$ 是 Type A 後綴， $y+1$ 是 Type B 後綴，直接呼叫 $!cmp(y+1,x+1)$

圖3 展示了當前範例的合併結果，DC3 算法到這邊就結束了。

整體時間複雜度 $T(n)=T(2n/3)+\ord{n}=\ord{n}$，但要注意空間使用量
$$M(n) =
\begin{cases}
n + \delta(n) + 2, & n \leq 2 \\
n + \delta(n) + 2 + M\left(\left\lfloor \frac{2(n + \delta(n))}{3} \right\rfloor\right), & n > 2\end{cases}\\ \delta(n) = [n\equiv 1\left(\bmod 3\right)]$$

根據 AI 的推導 $M\left(n\right)\le 3n+\left\lfloor 4\log_{1.5}\left(n-2\right)\right\rfloor+1$。

圖3

2025/10/10 更新：有人發現我原始的程式碼在當 n%3=1 遞迴時在 Type B1 和 Type B2 之間沒有隔離符號，有可能導致這兩類後綴排序錯誤，聽說我一開始的參考資料 ([2009] 后缀数组——处理字符串的有力工具 by. 罗穗骞) 也有一樣的問題，因此我花了點時間重寫了 DC3 的教學。

錯誤原因如圖4 所示，若不加上這個哨兵字元的話，後綴 7 就不會被加入遞迴運算，這樣會導致某個 Type B1 後綴將不是自己正確後綴的 Type B2 後綴連接起來排序導致結果錯誤。

圖4

以下提供模板(註解是請 AI 寫的，拿掉之後程式碼應該會很短):

[ Suffix Array Prefix doubling algorithms ] 後綴數組倍增算法

後綴數組(又稱尾碼陣列)是一個十分強大的字串處理武器，大部分的問題都可以用它來解決，它可以幾乎做到所有後綴樹(Suffix Tree)能做到的事，所以這邊就不介紹後綴樹了

因為後綴數組可以由後綴樹進行遍歷轉換而來，而構造後綴樹僅需花費線性的時間，所以構造後綴數組的時間可為線性\(\ord N\)，但是後綴數組本身就是為了減少構造後綴樹的空間與代碼量而被發明出來的，直接由後綴樹轉換是沒意義的
但是仍然有其他線性構造後綴數組的方法，像是DC3、SA-IS等會在下一篇介紹，這次要講的是比較簡單常用的方法-----倍增法
關於後綴數組的使用說明可以參考《后缀数组——处理字符串的有力工具》
關於倍增法的說明可以參考 演算法筆記-SuffixArray 的部分
這邊提供\(\ord{N*logN*logN}\)及\(\ord{NlogN}\)的模板

\(\ord{N*logN*logN}\):
\(\ord{NlogN}\):
注意此方法必須要在字元集大小為常數的情況下有效，否則必須離散化

所需的陣列長度只需要與字串陣列相同即可
當然\(N*logN*logN\)的做法會比較值觀，\(NlogN\)的方法則是利用radix_sort進行的，radix_sort本來在倍增的時候要先排序第一關鍵字跟第二關鍵字，但是第二關鍵字排序的結果可以用已經求好的SA直接求出來
對radix_sort還不了解的人請看這個網頁:https://www.cs.usfca.edu/~galles/visualization/RadixSort.html
如果想對Suffix Array算法進行測試請使用這個Online Judge:
http://www.spoj.com/problems/SARRAY/

英文字母大小寫轉換特殊做法

假設有一個題目是這樣的:
        給定一串英文字母，請將大寫的部分轉成小寫，小寫的部分轉成大寫並輸出

一般我們會用if或是三元運算子做判斷，但是這太麻煩了
經過觀察發現，摁合一個小寫字母ascii與其對應的大寫字母ascii相差皆為32，
而其二進位編碼剛好允許透過 xor 32的方式進行轉換，但是32這個數字不好記，又可以發現ascii 32='空白'，而以下的code就可以將大小寫互換:

1 2 3 4 5 6 7 8

#include<stdio.h> char s[1000005]; int main(){ scanf("%s",s); for(int i=0;s[i];++i)putchar(s[i]^' ');puts(""); for(int i=0;s[i];++i)putchar(s[i]^32);puts(""); return 0; }

兩種寫法會有相同的效果

[ Suffix Automaton ] 後綴自動機

定義字串S的後綴自動機是一種自動機可以接受S的所有後綴，其狀態最多為2*strlen(s)-1個，雖然理論複雜，但其構造方式十分簡單，且它可以用來處理一些後綴數組或事後綴樹的問題，因此是一個十分強大的資料結構。
後綴自動機大致的構造方式是將字串擔一字元按順序進行插入，插入的均攤時間為\(\ord 1\)，關於詳細的情形可以在 http://blog.sina.com.cn/s/blog_70811e1a01014dkz.html 這個網站中得到
而關於複雜度及詳細的證明請參考陈立杰的簡報
關於狀態數為線性的證明在19~21頁，有詳細的圖文解說
這個網站包含其一些延伸資料結構http://maskray.me/blog/2013-05-10-suffix-automaton
為了減少記憶體的使用，以vector代替指標維護狀態
以下提供模板:

[ Aho-Corasick Automaton ] AC自動機

Aho-Corasick Automaton，該算法在1975年產生於貝爾實驗室，是著名的多模匹配算法之一
在了解AC自動機之前，必須先學會字典樹Trie的使用，簡單的來說，他是將KMP的fail函數應用在Trie做為失敗邊。
有\(n\)個字串\(B_0,B_1,...,B_{n-1}\) 要匹配字串\(A\)，則一般用KMP的算法會得到\(\ord{\sum_{i=0}^{n-1}(|A|+|B_i|)}\)，使用AC自動機的演算法其複雜度為\(\ord{|A|+\sum_{i=0}^{n-1}|B_i|}\)，必須用DP

關於AC自動機的介紹請看這裡

以下為AC自動機的模板

[ Knuth-Morris-Pratt Algorithm ] 克努斯-莫里斯-普拉特(KMP)算法

這是一個大家很常聽到的字串匹配演算法，較Z Algorithm複雜，但更為通用，C++的string就有內建(string::find)。假設要以B匹配A，則會先建立B的部分匹配表(又叫做失配函數)，其定義如下:
     fail(i)=max(滿足B[0,k]=B[i-k,i]的所有k)
同樣的也可以在線性時間來完成
對於KMP演算法的詳細情況請參考這裡
以下提供fail function陣列及匹配的實作

[ Manacher's algorithm ] Linear time Longest palindromic substring 線性最長回文子串

Manacher演算法是Z algorithm的變種，可以說是雙向的Z algorithm，複雜度也是\(\ord N\)
其Z function定義如下:
     Z(i)=以位置i為中心的最長回文半徑
但是這樣只能處理回文長度是奇數的子串，因此必須幫字串做一些修改

假設原來的字串是: "asdsasdsa"
修改後變成: "@#a#s#d#s#a#s#d#s#a#"
其中'@'及'#'為不同字元且皆未在原字串中出現過
其Z function陣列為: 0 1 2 1 2 1 6 1 2 1 10 1 2 1 6 1 2 1 2 1
則 最大的數字-1 (10-1=9)就是我們要的答案

這裡提供Manacher algorithm產生Z function陣列的實作:

[ Z algorithm ] Linear-time pattern matching 線性字串匹配 Z演算法

定義一個字串S的Z function:
    Z(i)=0 如果i=0 or S[i]!=S[0]     否則
    Z(i)=max(所有的k滿足 S[0,k-1]=S[i,i+k-1])
從Z function的定義，假設要在字串A裡面匹配字串B
可以先建構字串S=B+(A和B都沒有的字元)+A的Z function陣列
若Z[i]=lenB則表示在A[i-lenB]有一個完全匹配
這裡提供兩個可以\(\ord{N}\)時間求出Z function陣列的方法:

對一個特殊構建的數據strlen(s)=10000000其效率平均為
z_alg1:   0.106s
z_alg2:   0.089s
這兩種方法的想法是相同的
我們可以知道第一個方法是較為直觀好寫的，但是運算量較大且調用min函數的效率並不高
但仍在可接受的範圍

c++ rope 基本應用

rope(粗繩)是一個很強大的字串處理物件，聽說是為了與string(細繩)做對比才叫做rope的，其底層是一棵持久化平衡樹，因此在做合併或在中間插入的期望時間是logn

再使用rope前必須在前置作以下的處理

#include<ext/rope>
using namespace __gnu_cxx;

定義一個元素為char的rope:

rope<char> r;

其實rope本身為了方便已經將rope<char>重新定義為crope
因此也可以這樣寫:

crope r;

當然rope也可以存取非char的元素
只是有些操作會不支援(例如輸出操作)

對於rope的一些常用操作請參考由SGI網站翻譯的rope成員詳細說明
裡面整理了rope的各種函式及元素
且已經將其翻譯成中文方便閱讀

字典樹 Trie

今天完成了字典樹 Trie的模板，可以在O(N) (N=字串長度)的時間搜尋一個字串
插入的時間亦是O(N)，在字串匹配上有很大的幫助(AC字動機)，但是因為每個節點都要記錄所有字元，是非常耗空間的
通常將根節點設為"沒有字元"，若是想進一步了解Trie請自行google吧!
以下為模板:
跟stl map的用法類似
trie<int >t;  //定義一個存int的Trie
trie<int ,'a','z'>t  //定義一個字元範圍是'a'到'z'的Trie(預設是'A'~'z')
trie<int >::point_iterator it;  //定義一個節點迭代器
t.insert("asd",1);  //插入1到"asd"的位置(若原來已有值則覆蓋)，傳回插入節點的point_iterator
t.find("asd");  //傳回"asd"位置的point_iterator，若無資料point_iterator為NULL，請注意
t["asf"];  //若"asd"存在資料，傳回其引用位置，若不存在則插入並傳回其引用位置
t.erase("asd");  //刪除"asd"節點，若成功刪除則傳回true，失敗(無結點)則傳回false
t.size(); //傳回字串的總數
t.clear();  //清空trie