[ bipartite graph multiple matching ] 二分圖多重匹配增廣路算法

這種問題的題目通常是這樣:

給一張圖G有n1個點和n2個點，n1個點之間沒有邊，n2個點之間也沒有邊，但是n1和n2個點之間有m條邊(簡單的來說就是n1個點和n2個點的二分圖啦)，沒有重邊；其中n2個點每個點\(u\)都有一個可接受匹配數 \(c_u\)。
n1的點只能跟一個點匹配，但n2的點在不超過可接受匹配數的情況下，可以跟多個點匹配，求這張圖的最大匹配

通常可以利用拆點的方法或是flow來做，但是這樣空間跟效率都不是很好，這裡提供一個有效率的方法:

複雜度分析:
設n2個點每個點\(u\)都有一個值\(E_u\)表示和\(u\)相鄰的邊數，則總複雜度為
$$ \ord{n1*(\sum{c_u*E_u}+n1+n2)} $$

[ Edmonds's general graph matching algorithm ] 一般圖最大匹配

關於匹配的教學我全部寫在這份投影片裡了:https://jacky860226.github.io/general-graph-weighted-match-slides/#/
所以這裡直接提供模板:
注意這裡必須要是無向圖

[ Kuhn-Munkres Algorithm ] 二分圖最大權完美匹配KM算法

關於此算法的介紹及教學請看這份投影片，這篇文章注重於討論$\ord{N^4}$的slack優化及$\ord{N^4}$到$\ord{N^3}$的過程。

在網路上曾經看到這段話:

"實際上KM算法的複雜度是可以做到$\ord{N^3}$的。我們給每個y頂點一個“鬆弛量”函數slack，
每次開始找增廣路時初始化為無窮大。在尋找增廣路的過程中，檢查邊(i,j)時，如果它不在相等子圖中，則讓slack[j]變成原值與lx[i]+ly[j]-w[i,j]的較小值。這樣，在修改頂標時，取所有不在交錯樹中的Y頂點的slack值中的最小值作為d值即可。但還要注意一點：修 改頂標後，要把所有不在交錯樹中的Y頂點的slack值都減去d。"

這段話其實是錯的，請看底下的code:

$\ord{N^4}$常數優化版本
我們仔細看一下迴圈的層數。
第一層是一個for迴圈，執行N次；第二層有一個無線迴圈，但她最多執行N次；裡面有一個DFS，最多執行$\ord{N^2}$次，還有一些迴圈但是不影響複雜度所以不討論。
總複雜度是$\ord{N}*\ord{N}*\ord{N^2}$為$\ord{N^4}$，因此網路上大多數$\ord{N^3}$的code其實是錯的。

接下來看一下我修改後真正的$\ord{N^3}$code:
可以看到我在dfs裡面加了一個參數adjust，如果他是true，就跟原本的dfs沒兩樣，可以在找到增廣路後順便將增廣路擴充；如果他是false，整個dfs就變成只能判斷有沒有增廣路了。
主函數dfs的部分移到while的外面，而修改lx,ly和slack_y後的地方增加了一個迴圈來判斷這次的修改有沒有產生可行的增廣路，對於新增加的「等邊」，如果他有機會是增廣路的話，會對此「等邊」連像的點y進行dfs「判斷」有沒有增廣路(把adjust設成0)。如果有增廣路，就會跳出while，在進行一次dfs來擴充增廣路。
總複雜度是
$\ord{N}[第一層迴圈] * ( \ord{N^2}[dfs的時間] + \ord{N}[while的次數]*\ord{N} ) = \ord{N^3}$
這才是真正的$\ord{N^3}$算法，前者只是常數優化而已

最後是$\ord{N^3}$算法常數較小的版本:

[ Augmenting Path Algorithm ] 二分圖匹配增廣路徑演算法

就是一直找增廣路徑，找到不能再找就是最大匹配惹
複雜度\(\ord{n1*(m+n2+n1)}\)，用dinic會比較快但是code比較長
模板:

[ 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拼起來即可
以下提供模板:

[ 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/

[ 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函數的效率並不高
但仍在可接受的範圍