摘要

字串匹配演算法的類型：
　一、以字元為單位，
　　　位移、對齊、比對。
　　　請參考：http://www-igm.univ-mlv.fr/~lecroq/string/index.html。

　二、以位元為單位，
　　　轉換成數值，使用數學方法計算相似度。
　　　例如Shift-And Algorithm。

　三、以後綴為單位，
　　　採用Enumerate與Search分為兩步驟：枚舉T的所有後綴、搜尋開頭恰為P的後綴。
　　　例如把所有後綴丟進Trie、Tree、Array等資料結構，並進行排序，然後搜尋。

字串匹配演算法的類型：
　一、T與P的最長共同前綴（Longest Common Prefix）
　　適用情況：T為定值，P為變動值。
　　單一字串匹配：Z Algorithm。（P為定值，T為變動值。）
　　單一字串匹配：Suffix Array + Binary Search、Suffix Trie、Suffix Tree。
　　特色：LCP Array。

　二、P本身的次長共同前後綴（Longest Proper Prefix-Suffix）
　　適用情況：P為定值，T為變動值。
　　單一字串匹配：Morris-Pratt Algorithm。
　　多重字串匹配：Aho-Corasick Algorithm。
　　特色：可以轉換成自動機。

String Matching

中譯「字串匹配」。大意是：有兩個字串T和P，找出T當中是否有一段字串正好是P，並找出位置。可想作是從長篇文字中搜索一小段文字。

註：在字串匹配問題中，我們通常將兩字串的象徵符號取做T和P，T意指text，P意指pattern。

T: ababcabc，P: abc，T中有兩個地方出現P：

ababcabc    ababcabc
  |||            |||
  abc            abc

這裡先提供一個天真又單純的演算法：用窮舉法，把P對準T的各個位置，然後逐一比對各字元判斷一不一樣。時間複雜度為O(T * P)。

T: ababcabc，P: abc，依序將P向右移，逐一比對各字元：

0.          1.          2.
ababcabc    ababcabc    ababcabc
|||          |||          |||
abc          abc          abc
(X)          (X)          (O)

3.          4.          5.
ababcabc    ababcabc    ababcabc
   |||          |||          |||
   abc          abc          abc
   (X)          (X)          (O)

void string_match() { string t = "ababcabc", p = "abc"; // 用暴力法把P對準T的各個位置 for (int i=0; i<t.size(); ++i) { // P不會超出T右端 if (i + p.size() > t.size()) break; // 判斷一不一樣 bool match = true; for (int j=0; j<p.size(); ++j) if (t[i+j] != p[j]) { match = false; break; } if (match) cout << "T的第" << i << "個字元開始為P"; } }

次長的共同前後綴
【註：此概念目前尚未有專有名詞】

1.
T: aabzabzabcz
P: abzabc
以窮舉法的概念，依序將P向右移，一一比對字元。
當移到時下圖位置時，此時發現P僅有一部分匹配到T：

        V
  aabzabzabcz
   |||||
   abzabc

2.
目前匹配到的這一部分，可以好好利用：

  .abzab.....
   |||||
   abzab.

3.
嘗試挪動P。
挪動一個位置、挪動兩個位置、……，

  .abzab.....   .abzab.....   .abzab.....   .abzab.....   .abzab.....
    ||||           |||            ||             |                   
    abzab.         abzab.         abzab.         abzab.         abzab.

  (P shift 1)   (P shift 2)   (P shift 3)   (P shift 4)   (P shift 5)

3.
換個角度來看上述的行為。
挪動一個位置：看看abzab的後四個字元，是不是前四個字元。
挪動兩個位置：看看abzab的後三個字元，是不是前三個字元。
　　　⋮　　　　　　　　　⋮　　　　　　　　　　⋮

4.
目前匹配到的這一部分（P的某個前綴），abzab
它的「次長的共同前後綴」，ab
藉由「次長的共同前後綴」大幅移動P，可以略過許多步驟：

        V                  V
  aabzabzabcz        aabzabzabcz
   |||||       --->      ||
   abzabc                abzabc

5.
由「V」處繼續往右進行字元比對。
如果還是不同字元，就再用相同手法挪動P。

以窮舉法進行字元比對的途中，每次要移動P時，就先取出P中有匹配到的前綴部分，求其「次長的共同前後綴」，然後以此大幅移動P，而不必一次移動一個位置。

註：當一個字串的某個前綴等於某個後綴時，就把此前綴，稱做該字串的「共同前後綴」。一個字串其「最長的共同前後綴」就是原字串本身。

演算法

1. 從左到右，依序比對字元。
2. 比對結果不同時，
   就從目前匹配到的部份字串，
   找到「次長的共同前後綴」來大幅移動P。
   然後繼續 1.。

甲、移動「V」。
　　（下一步為乙。）
乙、比對兩字元。
　　（若相同，下一步為甲或戊。若不同，下一步為丙。）
丙、從目前匹配到的部分字串，找到「次長的共同前後綴」。
　　（下一步為丁。）
丁、把P整個往右挪動，左端僅露出一截「次長的共同前後綴」。
　　（下一步是乙。）
戊、整個P匹配成功。
　　（下一步是丁。）
　　（當字串結尾附有'\0'，則下一步可改為甲。）

© 2010 tkcn. All rights reserved.

failure function（prefix function）

它是一個字串函數：輸入字串的其中一個前綴，則輸出該前綴的「次長的共同前後綴」。

會被稱作prefix function，是因為此函數的定義域是前綴。會被稱作failure function，是因為此函數的值域，是每次當P僅有一部分匹配到T（比對失敗了）的時候，緊接著得用到的資訊。這兩種講法都有人在用。

實作程式碼時，我們可以預先算好P的failure function。如此一來，進行字元比對時，就不必一直重算。

這裡使用Dynamic Programming來計算failure function。分割問題的方式，是把P[0...i]的最後一個字元拿掉，然後利用已求得的「次長的共同前後綴」，計算出P[0...i]的「次長的共同前後綴」。

// p[0...i] 的「次長的共同前後綴」是 p[0...failure[i]]。 // failure[] 值為 -1 時，代表「次長的共同前後綴」為空字串。 int failure[100]; void failure(string& p) { // iterative, bottom-up DP for (int i = 1, j = failure[0] = -1; i < p.size(); ++i) { // 先試 p[0...i-1] 的「次長的共同前後綴」p[0...j]， // 再試 p[0...j] 的「次長的共同前後綴」…… while (j >= 0 && p[j+1] != p[i]) j = failure[j]; // p[i] 終於有用處了，終於可以加長！ if (p[j+1] == p[i]) j++; // 得到了 failure[i] 的值！ failure[i] = j; } }

字串匹配

字串匹配的過程，跟failure function的計算過程十分相像，非常神奇。

int failure[100]; // P進行大幅移動後，所要對準的位置。 void Morris_Pratt(string& t, string& p) { if (p.size() > t.size()) return; // 預先算 P 的 failure function，O(P)。 for (int i = 1, j = failure[0] = -1; i < p.size(); ++i) { while (j >= 0 && p[j+1] != p[i]) j = failure[j]; if (p[j+1] == p[i]) j++; failure[i] = j; } // 進行字串匹配，O(T)。 for (int i = 0, j = -1; i < t.size(); ++i) // for (int i = 0, j = -1; i-j-1+p.size() <= t.size(); ++i) { // 先試 p[0...j] 的「最長的共同前後綴」， // 再試「次長的共同前後綴」， // 再試「次次長的共同前後綴」…… while (j >= 0 && p[j+1] != t[i]) j = failure[j]; // t[i] 終於有用處了，終於可以加長！ if (p[j+1] == t[i]) j++; // 匹配到了整個 P！ if (j == p.size()-1) { cout << "P的出現位置是" << i - p.size() + 1; // 如果字串結尾是'\0'的時候，就可省略這三行。 // 如果字串結尾不是'\0'的時候，就必須先挪動 P。 j = failure[j]; i--; continue; } } }

時間複雜度：multipop stack的均攤分析

權且討論另外一個問題。

有一個stack，一開始是空的。它有三種操作。

1. push(x)      - worst time O(1)
2. pop()        - worst time O(1)
3. multipop(k)  - 連續pop出k個元素，如果stack是空的就馬上停止。
                  worst time O(min(k, s))，當stack恰有s個元素的時候。

請問這個stack進行N次操作的時間複雜度為多少？
當然我們不知道每次的操作是哪一種。可能是三種其中一種。

甲、一般的分析方法。時間複雜度最大的就是multipop，所以我們可以把最差的情形想做是N次multipop。一次multipop的時間複雜度是O(min(n, k))，n和k最大可到N，因此最差是O(N)。N次的multipop最差是O(N^2)，因此答案就是O(N^2)。

乙、均攤分析中的聚合分析。N次操作從頭到尾最多只能放進N個元素到stack，也就是N次push。這也就是說，stack從頭到尾最多就只能彈出N個元素，更精準的來說是N/2個元素。不論是用pop彈，或者是用multipop彈，最多就是都是彈出N/2個元素。現在由放入的元素、彈出的元素的總數量，來計算時間複雜度；這兩個數量相加最多就是N，因此答案就是O(N)。

時間複雜度

接著回到Morris-Pratt Algorithm。以字元兩兩比對的總次數，作為時間複雜度。

甲、進行字串匹配的過程：觀察一下當下匹配到的字串片段S，想成是stack的元素。一開始S長度是零。每當比對到相同字元，S就會增加一字元，就是push；如果比對到不同字元，就要開始找次長共同前後綴，S一瞬間變短很多，就是multipop（實際上「S一瞬間變短很多」只需要O(1)，時間複雜度遠比multipop來的小。）。運用前面的分析方式。最多有T個字元丟入S，因此最多有T個字元從S彈出，因此可知字元兩兩比對的總次數不超過2*T次。

換個方式說。對於T的某一個字元來說，其進行字元兩兩比對的次數，會小於等於當下「P中有匹配到的前綴」長度。「P中有匹配到的前綴」長度是動態改變的，其長度如同stack一樣增減，因此可知字元兩兩比對的總次數不超過2*T次。

乙、計算P的failure function的過程：原理與甲相同，字元兩兩比對的總次數不超過2*P次。

故時間複雜度總共為O(T + P)。

UVa 10298 11475

延伸閱讀：Morris-Pratt Automata

此演算法可以化作自動機，轉化的時間複雜度為O(PA)，A為字元種類數目。

化作自動機之後，字串匹配的過程就變得更簡單了，甚至可以設計成電子迴路。

轉化的原理，是針對每個狀態，都找出經由failure function能到達的狀態們，然後建立轉移邊，連到那些狀態們的下一個狀態。

【待補程式碼】

註記

幾乎所有坊間書籍都將Morris-Pratt Algorithm誤植為KMP Algorithm，連CLRS也不例外。

中文網路流傳著一個Extended KMP Algorithm，學術上查無此稱呼。究其內容，實為Z Algorithm。

演算法

           v
T = aaaabcacab
P =    abcabcacab
           ^

Morris-Pratt Algorithm當中，當比對到此處，發現c != b，所以需要往右移動P。找到abca的相同前後綴，也就是a。然後往右移動P，讓左端凸出一段a。

           v
T = aaaabcacab
P =       abcabcacab
           ^

接下來就繼續比對c與b了。在這裡c != b，所以又要移動P了。

Knuth則是多想了一步：連續移動P，能不能預先偵測到呢？Knuth發現一件事，當我們找到abca的相同前後綴a之後，我們可以看看abca的下一個字元（是b），是不是剛好為a的下一個字元（也是b）。如果兩個字元一樣的話，那就表示P鐵定會連續移動兩次，兩次比較都是c != b。

既然鐵定會移動兩次，那乾脆直接移到定位不就好了？於是Knuth在計算failure function的時候，就額外加了一個判斷：找到abca的相同前後綴f(abca) = a之後，如果f(abca)的下一個字元恰好是abca的下一個字元，那麼就令f(abca) = f(a)，也就是再多找一次a的相同前後綴。如此一來，P只要移一次就行了。

由於failure function計算方式是遞迴定義的，所以連續移動三次、四次、五次的情況，經過遞迴計算的過程後，最後都會變成一次移到定位。

延遲時間

當T是一個stream I/O、讀入字元只能一個一個來的情況下，每讀入一個字元最多會有1+log_φP次字元比較。換句話說，每讀入一個字元，直到需要讀取下一個字元前，期間最多會停滯O(log_φP)的時間。

【待補證明】

演算法

請參考：http://www.cs.uku.fi/~kilpelai/BSA05/lectures/slides04.pdf

Applet：http://www-sr.informatik.uni-tuebingen.de/~buehler/AC/AC1.html

可以一口氣同時匹配很多個P的演算法，概念與Morris-Pratt Algorithm相同。預先把所有P建成一棵trie，並預先在trie上建立好failure link，然後就可以拿trie與T進行字串匹配了。

Morris-Pratt Algorithm的原理，是以當下匹配到的部份，找出次長共同前後綴，是在P的那個位置。Aho-Corasick的原理，是以當下匹配到的部份，找出次長共同前後綴，是在那一個Pi的那個位置。差別就是：前者只有一個P可以找，後者有P1到Pn可以找。

如果P之中有父子關係（一個字串是另一個字串的子字串），trie上就必須再額外建suffix link，才能把所有匹配到的字串全部找出來。

UVa 10679

時間複雜度

O(T + (P1 + ... + Pn) + K) = O(T + Σ(Pi) + K)，K是各個P在T中的出現次數的總和。也可以省略K，寫成O(T + Σ(Pi))，甚至寫成O(T + P)。

int N = 1000; // P的個數 char T[1000+1]; char P[1000][1000+1]; bool occur[1000+1]; // 記錄各個P有沒有出現在T當中 int equiv[1000+1]; // 記錄相同字串之中index最小的 struct TrieNode { TrieNode* l[26], *failure, *suffix; int index; // P的編號 } *root; // 初始化 void init() { memset(trieNode, 0, sizeof(trieNode)); memset(occur, 0, sizeof(occur)); memset(equiv, 0, sizeof(equiv)); root = new TrieNode(); } // 砍掉整棵trie void free(TrieNode* p = root) { for (int i=0; i<26; ++i) if (p->l[i]) free(p->i[i]); delete p; } // 把一個字串加入trie void add(char* s, int index) { TrieNode* p = root; for (; *s; ++s) { if (!p->l[*s - 'A']) p->l[*s - 'A'] = new TrieNode(); p = p->l[*s - 'A']; } // 如果該字串之前有出現， // 就記錄index最小的那個字串， // 不然就直接加入trie即可。 if (p->index) equiv[index] = p->index; else p->index = index; } // 建立failure link和suffix link // 以BFS順序進行 // 時間複雜度O(Σ(Pi)) void build() { TrieNode* q[100000], **qf, **qb; qf = qb = q; *qb++ = root; while (qf < qb) { TrieNode* p = *qf++; for (int i=0; i<26; ++i) if (p->l[i]) { TrieNode* q = p->failure; while (q && !q->l[i]) q = q->failure; if (q) { p->l[i]->failure = q->l[i]; p->l[i]->suffix = (q->l[i]->index ? q->l[i] : q->l[i]->suffix); } else p->l[i]->failure = p->l[i]->suffix = root; *qb++ = p->l[i]; } } } // 拿trie與T進行字串匹配 // 時間複雜度O(T+K) void match(char* s) { TrieNode* p = root; for (; *s; ++s) { // 不斷嘗試比對目前的字元， // 比不到就跑failure link縮小後綴 // 整個函式前前後後，總計時間複雜度為O(T)。 while (p && !p->l[*s - 'A']) p = p->failure; if (p) p = p->l[*s - 'A']; else p = root; // 完整匹配了！ // 跑suffix link找出所有後綴，這些後綴都出現在P中。 // 整個函式前前後後，總計時間複雜度為O(K)。 if (p->index) for (TrieNode* q = p; q; q = q->suffix) occur[q->index] = true; } } int main() { init(); // 初始化 for (int i=0; i<N; ++i) add(P[i], i+1); // 所有P建成trie build(); // 建立failure link和suffix link match(T); // 拿trie與T進行字串匹配 free(); // 釋放記憶體空間 for (int i=1; i<=N; ++i) // 有匹配到的，或者之前有相同字串有匹配到的。 if (occur[i] || occur[equiv[i]]) cout << "第" << i << "個字串有出現"; else cout << "第" << i << "個字串沒出現"; return 0; }

延伸閱讀：使用n次Morris-Pratt Algorithm

想一口氣匹配很多個P，也可以用n次Morris-Pratt Algorithm，總時間複雜度就是O((T+P1) + ... + (T+Pn)) = O(n*T + Σ(Pi))。這法子比Aho-Corasick Algorithm慢上許多。

延伸閱讀：使用Suffix Tree

想一口氣匹配很多個P，有個更簡單的演算法：只要替T建立一棵suffix tree，看看樹上有沒有各個P即可。時間複雜度與Aho-Corasick Algorithm基本相同。不過這個方式適用於T是固定的時候，而Aho-Corasick Algorithm適用於P是固定的時候。

延伸閱讀：Aho-Corasick Automata【尚待確認】

此演算法可以化作自動機，轉化的時間複雜度為O(NA)，N為Trie的節點數目，A為字元總類數目。與Morris-Pratt Automata的建構原理一模一樣。

至於suffix link的部份，則無法輕易的轉換成自動機，姑且略過不提。

void build_automata() { // 使用BFS順序建立自動機 TrieNode* q[100000], **qf, **qb; qf = qb = q; *qb++ = root; // 比對失敗，狀態轉移到root。 // 比對成功，狀態轉移到對應字元。設定好failure link。 for (int i=0; i<26; ++i) if (!root->l[i]) root->l[i] = root; else { root->l[i]->failure = root; *qb++ = root->l[i]; } // 比對失敗，狀態轉移到適當的共同前後綴，再加一個字元。 // 比對成功，狀態轉移到對應字元。設定好failure link。 while (qf < qb) { TrieNode* p = *qf++; for (int i=0; i<26; ++i) { if (!p->l[i]) p->l[i] = p->failure->l[i]; else { p->l[i]->failure = p->failure->l[i]; *qb++ = p->l[i]; } } } }

ICPC 3124

延伸閱讀：Wild Card String Matching

當P中含有萬用字元「?」的時候，可以將P拆成一段一段不含萬用字元的部份，然後使用Multi-Pattern String Matching求出各小段在T中的出現位置，然後位移對齊一下（根據各小段在P中的位置），看看P的所有小段是否同時出現，即代表是否有匹配。時間複雜度是O(T+P)。

UVa 475

演算法

當T與P是二維長方形的時候。時間複雜度是O(T+P)。

1.
把T橫切成一條一條，
把P橫切成一條一條，
然後每一條T都執行Multi-Pattern String Matching，例如Aho-Corasick Algorithm。
如果第a條P，從T[i,j]開始出現，那麼就進行紀錄：M[i,j] = a。
M是一個跟T一樣大的陣列。

2.
把M直切成一條一條，
每一條M都執行String Matching，例如Morris-Pratt Algorithm。
看看是否出現1234567...n這個字串（剛剛P共有n條）。

X.
當P有某兩條相同時，則要小心處理，把這兩條的編號設為相同。

附帶一提，如果是使用Aho-Corasick Algorithm，因為P中不會有父子關係，所以不必建suffix link，省下很多功夫。

UVa 11019

Boyer-Moore Algorithm

【待補文字】

Z function

定義一個函數Z()，Z(i)是指由s[i]開始的字串，與s[0]開始的字串可以匹配到多長。也就是說s[0 ... Z(i)-1] = s[i ... i+Z(i)-1]。

  | 0 1 2 3 4 5 6 7
--+-----------------
s | a b a a b a a b
z | 8 0 1 5 0 1 2 0

Z(0)：abaabaab，長度8。
Z(1)：ф，長度0。
Z(2)：a，長度1。
Z(3)：abaab，長度5。

設計此函數的緣由，是因為進行字串匹配的時候，我們總是希望兩字串的開頭盡可能長得一樣。至於為什麼取名為Z，就得問原作者了。後面將提到如何運用Z function作字串匹配，現在先講解如何計算Z function。

計算Z()，是由左往右算。Z(0)是特例，Z(0)是整個字串的長度，所以Z(0)不用算，由Z(1)開始算。

計算Z(i)，是運用已經算好的Z(j)，j < i。也就是指某一段已經算好的s[0 ... Z(j)-1] = s[j ... j+Z(j)-1]。首先找出有覆蓋到s[i]的s[j ... j+Z(j)-1]是那一段，而且j+Z(j)-1越右邊越好。

一、如果找不到可以覆蓋s[i]的s[j ... j+Z(j)-1]，表示已經算好的部份都派不上用場。從s[i]與s[0]開始比對，逐字比下去。

二、如果找到可以覆蓋s[i]的s[j ... j+Z(j)-1]，表示s[i]也會出現在s[0 ... Z(j)-1]之中，把i映射到對應的位置i'。接著再來一次，運用Z(i')，也就是指s[0 .... Z(i')-1] = s[i' ... i'+Z(i')-1]，如此又可以把i'映射到字串的最前頭了。

二之一、如果s[i ... i+Z(i')-1]短少於s[j ... j+Z(j)-1]的右端，那就可以直接算出Z(i)的答案，就是Z(i')。

二之二、如果s[i ... i+Z(i')-1]剛好貼齊s[j ... j+Z(j)-1]的右端，那就必須檢查未確定的部分，直接從s[j+Z(j)]與s[j+Z(j)-i]繼續比對，逐字比下去。

二之三、如果s[i ... i+Z(i')-1]突出了s[j ... j+Z(j)-1]的右端，則與上一種情形相同。

時間複雜度

以字元兩兩比較的總次數，作為時間複雜度。

j+Z(j)-1這個數值會從0開始不斷增加。每當字元比對成功時，j+Z(j)-1就會跟著增加，下次比對的時候就會從j+Z(j)繼續比對。j+Z(j)-1這個數值的增加次數與比對次數一樣多，最多會從0增加到S，所以時間複雜度是O(S)。

j便是原著中的L，j+Z(j)-1便是原著中的R。

void z_function(string& s) { vector<int> Z(s.size(), 0); // 建立z陣列，初始化為0。 Z[0] = s.size(); int L = 0, R = 0; // s[L, R]即是s[j ... j+Z(j)-1]。 for (int i=0; i<s.size(); ++i) { // i' // 因為l移動到0，減了l；所以i移動到i-l，減了l。 int ii = i - l; // j+Z(j)映射到字串開頭的位置 // 因為i移動到0，減了i；所以r+1移動到r+1-i，減了i。 int n = R + 1 - i; // 已經算好的部份都派不上用場 if (i > R) { // 從s[i]與s[0]開始比對，逐字比下去。 int x = i; while (x < s.size() && s[x] == s[x-i]) x++; z[i] = x - i; // 更新s[0 ... Z(j)-1] = s[j ... j+Z(j)-1]。 if (x > i) L = i, R = x - 1; } // s[i ... i+Z(i')-1]貼齊或超出s[j ... j+Z(j)-1]的右端 else if (Z[ii] > n) { // 從s[R+1]與s[R+1-i]開始比對，逐字比下去。 int x = R + 1; while (x < s.size() && s[x] == s[x-i]) x++; Z[i] = x - i; // 更新s[0 ... Z(j)-1] = s[j ... j+Z(j)-1]。 L = i, R = x - 1; } else { Z[i] = Z[ii]; } } }

字串匹配

只要弄出P + $ + T，也就是把P接到T開頭，中間用一個從未出現過的字元隔開。然後算一次Z()，看看哪些Z(i) 剛好是P的長度，就匹配完畢了。

實作時不必真的把T與P接在一起，可以先算好P的Z function，然後再利用P去計算T的Z function就可以了。時間複雜度為O(T+P)。

映射至P的過程，就宛如Morris-Pratt Algorithm當中的「次長共同前後綴」。

Z Algorithm           ：一個字串的每個後綴之中，與字串開頭相同的最長前綴。
Morris-Pratt Algorithm：一個字串的每個前綴之中，與字串開頭相同的次長後綴。

Z Algorithm點明了字串匹配的精髓，就是兩個字串的「共同前綴」，非常直觀。Morris-Pratt Algorithm可視作Z Algorithm的另外一面，兩者關係互補。