String Matching

String

「字串」由一串字元所構成。例如aaabbbccc、48Dfua@~!0Hrb、m、How are you?等都是字串。有個特例是空字串:一個字元都沒有的字串。

字串的長度就是一個字串擁有的字元數目。空字串就是長度為零的字串。

Character

「字元」是字串的基本單元,一個字串當中的每個符號皆是字元,例如字串How are you?的字元依序為:H、o、w、 、a、r、e、 、y、o、u、?。字串How are you?的第一個字元為英文字母H,第三個字元為英文字母w,第四個字元為空白符號 。最後一個字元為問號?。

附註:中文句子的各個文字也都是字元。例如「你好嗎?」的第二個字元是「好」,第四個字元是全形問號「?」。

附註:ASCII 表列出了電腦中常見的128種字元,包括大小寫英文字母、標點符號阿拉伯數字、數學運算符號、其他雜七雜八的符號等等。

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)

事實上字串比對的問題早已有很多O(T + P)時間的演算法了,各位可以參考:http://www-igm.univ-mlv.fr/~lecroq/string/index.html。接下來我們只介紹幾個經典的字串比對演算法。

String Matching: Knuth-Morris-Pratt Algorithm

Knuth-Morris-Pratt Algorithm

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

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

T = aabzabzabcz、P = abzabc,依序將P向右移進行字串比對。
當移到時下圖位置時,此時發現P僅有一部分匹配到T:

aabzabzabcz
 |||||
 abzabc

此時取出P的前綴,並且是有匹配到T的那一段前綴:abzab
接著找出abzab的「次長的相同前後綴」:ab
以ab來大幅移動P,略過許多不必要的比對位置:

     V                  V
aabzabzabcz        aabzabzabcz
    ||        >>>      ||
 ab-ab-                ab----

各位可以自行證明一下,這般大幅移動,為何仍可得到正確結果?

failure function(prefix function)

它是一個字串函數:輸入一個前綴,輸出該前綴的「次長的相同前後綴」。

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

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

字串比對

時間複雜度

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

一、進行字串比對的過程:對於T的某一個字元來說,其進行字元兩兩比對的次數,會小於等於當下「P中有匹配到的前綴」長度。「P中有匹配到的前綴」長度是動態改變的,採用堆疊的均攤分析手法,可知字元兩兩比對的總次數不超過2*T次。

二、計算P的failure function的過程:同理,字元兩兩比對的總次數不超過2*P次

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

UVa 10298 11475

Multi-Pattern String Matching:
Aho-Corasick Algorithm

Aho-Corasick Algorithm

可以一口氣比對很多個P的演算法,時間複雜度是O(T + (P1 + ... + Pn) + K) = O(T + Σ(Pi) + K),K是各個P在T中的出現次數的總和。

想一口氣比對很多個P,也可以用n次KMP Algorithm,總時間複雜度就是O((T+P1) + ... + (T+Pn)) = O(n*T + P),n是P的總個數。這法子比Aho-Corasick Algorithm慢上許多。

想一口氣比對很多個P,有個更簡單的演算法:只要替T建立一棵suffix tree,看看樹上有沒有各個P即可。時間複雜度與Aho-Corasick Algorithm基本相同。

演算法

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

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

概念上和KMP Algorithm相同。預先把所有P建成一棵trie,並預先在trie上建立好failure link,然後就可以拿trie與T進行字串比對了。

如果P之中有父子關係(一個字串是另一個字串的子字串),就必須再建suffix link,並改寫程式,以達到O(T + Σ(Pi) + K)的時間複雜度。

一口氣比對很多個字串

UVa 10679