計算機算法基礎(chǔ) 第2版 課件 第13章 字符串匹配

1第13

章

字符串匹配字符串匹配的定義

2

一個樸素的字符串匹配算法

4Rabin-Karp算法

5基于有限狀態(tài)自動機的匹配算法

11Knuth-Morris-Pratt(KMP)算法

241.字符串匹配的定義2許多應(yīng)用問題需要確定一個給定的模式是否在一個文本中出現(xiàn)，并找出這個模式在文本中所有出現(xiàn)的位置。例如，在編輯文章時，我們希望找出一個單詞出現(xiàn)的所有地方。文本(text)：

是一個有序的符號序列，符號取自一個給定的符號集合

。例如，

={0，1}，那么，一個文本就是一個只含0和1的字符串。通常我們用數(shù)組T[1..n]表示一個有n個字符的字符串或簡稱為串。模式(pattern)：是另一個取自相同符號集的子符串，通常用P[1..m]表示一個有m個字符的模式(m

n)。3定義13.1給定文本T[1..n]和模式P[1..m](m

n)，文本的子串T[s+1..s+m]稱為有位移

s的字符段，記為

Ts

=T[s+1..s+m]

(0

s

n-m)。如果有Ts

=P[1..m]，那么我們說，文本左移s個位置后與模式P匹配，并稱s是個合法的移位。定義13.2給定一個文本T[1..n]和一個模式P[1..m](m

n)，字符串匹配問題就是找出模式P與文本T所有匹配開始的位置，也就是找出所有合法的移位。4這是一個簡單的貪心法。它從左到右，一個一個字符匹配。Naive-String-Matching(T[1..n]，P[1..m])fors

0to

n-m

ifP[1..m]=T[s+1..s+m]

thenprint“avalidshift”s endifendforEnd這個樸素的算法有較高的復(fù)雜度O(m(n-m))。2.一個樸素的字符串匹配算法TPs=3abaacabaabcabacbas=1s=2s=0例13.1s=3是合法移位5為簡單起見，先用

={0,1,...,9}為例來解釋。主要思路是：把P[1..m]看作一個m位的十進制數(shù)字，并假設(shè)它的值是p。移位s的字符段Ts

=T[s+1..s+m]也視為有m位的一個十進制數(shù)字，并假設(shè)它的數(shù)值是ts。如果移位s是個合法移位，則必有

ts=p。我們用Horner法計算P[1..m]的值p:p=P[1..m]=P[1]

10m-1+P[2]

10m-2+…+P[m-1]

10

+P[m]=P[m]+10(P[m-1]+10(P[m-2]+…+10(P[2]+10P[1])…))。例如，P[1..4]=2463,那么p=3+10(6+10(4+10(2)))。當(dāng)

是任意集合時，如果|

|=d，我們把

中符號與0到d-1

的d個數(shù)字，0,1,2,…,d-1，建立一一對應(yīng)關(guān)系，那么P[1..m]則對應(yīng)一個m位的d進制數(shù)p。3.Rabin-Karp算法6當(dāng)

是任意集合時，|

|=d，這時Horner公式為：p=P[m]+d(P[m-1]+d(P[m-2]+…+d(P[2]+dP[1])…)) (13.1)例13.2 假設(shè)

是26個英語字母的集合，我們把字母從a到z順序?qū)?yīng)到數(shù)字0到25，請計算P[1..4]=dfaz對應(yīng)的數(shù)值p。解：

因為字母d對應(yīng)于3，f對應(yīng)于5，a對應(yīng)于0，z對應(yīng)于25，所以有： p=25+26(0+26(5+26

3))=56133。

顯然，計算P[1..m]的值只需O(m)時間。計算ts

的值顯然，計算t0

的值也只需O(m)時間。而得到t0

之后，計算t1只需要常數(shù)時間就可以了。具體公式為：

t1 =T[2..m+1]=T[m+1]+dT[2..m] =T[m+1]+d(T[1..m]–dm-1T[1]) =T[m+1]+d(t0–dm-1T[1])7計算ts

的值(繼續(xù))所以，從t0算t1只要O(1)時間。接下來，可順序算出t2，t3，…等。從ts計算ts+1的迭代公式是：Tts+1=T[m+s+1]+d(ts

–dm-1T[s+1]) (13.2)因此，我們用O(m)時間算出p=P[1..m]、t0=[1..m]、和dm-1之后，只需O(n-m)時間就可以找出所有的匹配的合法移位。問題：上面的做法有個條件，就是在用公式(13.1)和(13.2)時，每一步的算術(shù)操作必須能在常數(shù)時間內(nèi)完成。這個要求在m和n很大時不可能，因為乗積會很大，遠大于計算機一個存儲單元的容量。解決方法：我們選一個合適的質(zhì)數(shù)q作模數(shù)，使所有的運算都是在模q下進行。這樣一來，所有算術(shù)運算的結(jié)果值都不超過q。我們選質(zhì)數(shù)q使得乘積dq可以存放在計算機一個單元內(nèi)。同時，上面的迭代公式(13.1)和(13.2)也相應(yīng)地修改為：

(見下頁)8p=(P[m]+d(P[m-1]+

…+d(P[2]+(dP[1])mod

q)…)mod

q)mod

q (13.3)ts+1=(T[m+s+1]+d(ts

-hT[s+1]))modq (13.4)這里，h=dm-1

mod

q，可預(yù)先在O(m)時間內(nèi)算好。p=P[1..m]和t0=T[1..m]也可在O(m)時間內(nèi)先算好。算出p、t0、和h之后，可逐個算出ts

(1

s

n-m)并與p匹配。匹配操作：for

s

0to

n–m

如果p

ts時，s不是一個合法移位。如果p=ts時，檢查是否真的有P[1..m]=T[s+1..s+m]。 //因為

pmod

q=tsmod

q

不一定導(dǎo)致p=

ts endfor(完整偽碼見下頁)9Rabin-Karp-Matching(T[1..n],P[1..m],d,q)h

1

//初始化hfori

1to

m–1 h

d

hmod

qendfor //得到

h=dm-1

modqp

P[1]

//初始化pt0

T[1]

//初始化t0fori

2to

m

//匹配前預(yù)處理，計算p

和t0

p

P[i]+(d

p

mod

q)

//公式(13.3)

t0

T[i]+(d

t0

mod

q)

endforp

p

mod

qt0

t0

mod

q

//最后一步算p和t0

(接下頁)10Rabin-Karp-Matching(繼續(xù))for

s

0to

n–m //匹配開始 ifp=ts then if

P[1..m]=T[s+1..s+m] //檢查真?zhèn)?/p>

thenprint“avalidshift”s

endif endif ifs<n-m

then

ts+1

(T[m+s+1]+d(ts

-hT[s+1]))

modq

//公式(13.4)

endifendforEnd Rabin-Karp算法需要

(m)時間算出p、t0、和h。最壞情況下，它需要

(m(n-m))時間做匹配檢查。所以，它的最壞情況復(fù)雜度是O(m(n-m))。但是，如果合法移位的個數(shù)是常數(shù)，那么算法的復(fù)雜度為O(n)。114.基于有限狀態(tài)自動機的匹配算法有限狀態(tài)自動機簡介一個有限狀態(tài)自動機(finitestateautomaton,FSA)M是一個

5元組(Q,q0,A,

,

)，其中，Q

一個有限個狀態(tài)的集合；q0

是Q中的一個狀態(tài)，q0

Q，被指定為初始狀態(tài)；A

是Q的一個子集，A

Q，它的狀態(tài)被指定為接收狀態(tài)；

有限個輸入符號的集合；

狀態(tài)轉(zhuǎn)換函數(shù)

:Q

Q。12自動機M對字符串w進行識別的算法M一開始是在初始狀態(tài)q0。然后，按照串w中字符順序，逐個字符掃描。如果它的當(dāng)前狀態(tài)，即掃描某個字符a之前的狀態(tài)是q，那么它掃描字符a后進入的狀態(tài)由狀態(tài)轉(zhuǎn)換函數(shù)決定。

如果

(q，a)=q’，那么自動機M

進入狀態(tài)q’。

這里，q’是Q中另一個狀態(tài)，也可能q’=q，狀態(tài)不變。串w中每個字符都被掃描后自動機M進入的狀態(tài)稱終止?fàn)顟B(tài)。如果終止?fàn)顟B(tài)是一個接收狀態(tài)，那么我們說自動機M接收字符串w，否則拒絕w。如果在掃描過程中某一步，自動機M進入了一個接收狀態(tài)，那么我們說自動機M接收當(dāng)前已被掃描過的字符形成的字符串。13例13.3假設(shè)我們有自動機，M=(Q,q0,A,

,

)，其中，Q ={0,1}；q0 =0；A ={1}；

={a,b}；

={

(0,a)=1,

(0,b)=0,

(1,a)=0,

(1,b)=0}。請判斷M是否接收w=abba。解：轉(zhuǎn)換函數(shù)

可以用一個表格表示：

輸入符號狀態(tài)ab010100從q0開始，自動機對w=abba逐字掃描后的狀態(tài)順序為：q0=0,

(0,a)=1,

(1,b)=0,

(0,b)=0,

(0,a)=1。所以M接收w=abba?？珊喕癁椋?/p>

(q0,w)=

(0,abba)=

(1,bba)=

(0,ba)=

(0,a)=1。14一些有關(guān)概念和術(shù)語由字符集

中字符組成的所有字符串，包括空串

在內(nèi)，的集合稱為全語言并記為

*。自動機M實際上定義了一個從

*到狀態(tài)集合Q的函數(shù)

:

*

Q，稱為最終狀態(tài)函數(shù):

給定w

*，如果w=

，那么

(

)=q0，否則

(w)=

(q0,w)。即，w的最終狀態(tài)函數(shù)值就是M掃描w后的終止?fàn)顟B(tài)。自動機M可以等價地用一個有向圖表示。圖中每一個點(小圓圈)對應(yīng)于一個狀態(tài)、如果有

(u,a)=v，則有一條標(biāo)號為a的邊(u,v)。另外，用一個箭頭(不計入圖的邊)指向?qū)?yīng)于初始狀態(tài)q0的頂點，而對每一個接收狀態(tài)對應(yīng)的頂點用雙層圓圈標(biāo)出。15例: 對應(yīng)于例13.3中的自動機，M=(Q,q0,A,

,

)，其中，Q ={0,1}；q0 =0；A ={1}；

={a,b}；

={

(0,a)=1,

(0,b)=0,

(1,a)=0,

(1,b)=0}。

輸入符號狀態(tài)ab01010016

17字符串匹配用的自動機的構(gòu)造給定

和P[1..m]后，自動機M=(Q,q0,A,

,

)定義如下：Q={0,1,2,…,m}；q0=0；A={m}；

(q,a)=

(Pqa)，這里a是

中任一字符?；舅悸罚簭腡[1]開始，逐字掃描T[i]。如果

(T[1..i])=q，那么進入狀態(tài)q。如果s是合法移位，那么在掃描T[s+m]后會進入狀態(tài)m而被發(fā)現(xiàn)。假設(shè)掃描T[1..i]后的狀態(tài)是q，即

(T[1..i])=q。如果T[i+1]=a，那么T[1..i+1]的后綴函數(shù)就等于Pqa的后綴函數(shù)

(Pqa)。(見下圖)18圖13-419例13.5假設(shè)有字符集

={a,b,c}和模式P=abca，請用有向圖描述用于匹配該模式的有限狀態(tài)自動機。解：下圖(13-5)中有向圖表示了這個自動機，它的轉(zhuǎn)換函數(shù)是由直接觀察得到的。a0123cbaaab,c4cbbcab,c給定字符集

和模式P[1..m]后，構(gòu)造自動機的工作主要是計算狀態(tài)轉(zhuǎn)換函數(shù)

(Pqa)。這可由下面算法完成。20

21基于有限狀態(tài)自動機的串匹配算法構(gòu)造好一個用于匹配的有限狀態(tài)自動機以后，文本串中所有合法移位可由下面算法找到。Finite-Automaton-Matcher(T[1..n],

,m)q

0fori

1to

n

q

(q,T[i]) ifq=m thenprint

“Patternoccurswithshift”i–m endifendforEnd算法Finite-Automaton-Matcher只需O(n)時間。如果加上構(gòu)造自動機的時間，總的復(fù)雜度是O(n+m3|

|)。22例13.6假設(shè)有字符集

={a,b,c}和模式P=abca，請解釋算法Finite-Automaton-Matcher是如何用有限狀態(tài)自動機找出文本T=cabcabcab的所有合法移位的。解：這個模式對應(yīng)的自動機已由圖13-5給出。這題的文本串有9個字母。下圖(13-6)列出了上面算法(第3行)用自動機的狀態(tài)函數(shù)掃描每個字符T[i]，i=1,2,…,9,后所得的狀態(tài)q值。算法在掃描字符T[4]和T[7]后發(fā)現(xiàn)兩處成功匹配，其合法移位分別是1和4。(見下頁)23a0123cbaaab,c4cbbcab,ci開始前123456789T[i]

cabcabcab狀態(tài)q0012342342合法移位----------1----4--245.Knuth-Morris-Pratt(KMP)算法和基于自動機的算法相似，也是逐字掃描T[i]并計算T[1..i]的后綴函數(shù)

(T[1..i])。如果發(fā)現(xiàn)

(T[1..i])=m，則發(fā)現(xiàn)一個合法移位。KMP不預(yù)先計算轉(zhuǎn)換函數(shù)。掃描T[i]后，不能立即得到

(T[1..i])。而是要臨時計算。KMP也需要預(yù)處理，但不是計算轉(zhuǎn)換函數(shù)

，而是計算“前綴函數(shù)”

[1..m]，并且只需要O(m)時間。前綴函數(shù)

[1..m]幫助KMP，在掃描T[i]后，快速地實時地計算

(T[1..i])。KMP掃描字符T[i]時，雖然要多化些時間去臨時計算

(T[1..i])，但保證總的匹配時間仍是線性時間O(n)，并省去了費時的預(yù)處理時間。25

26答案：因為

(T[1..i])=q，T[i+1]=a，那么T[1..i+1]的后綴函數(shù)也就是Pqa的后綴函數(shù)

(Pqa)。基于自動機的算法的做法是：預(yù)先算好Pqa的后綴函數(shù)，

即轉(zhuǎn)換函數(shù)

(q,a)，可立即得到

(T[1..i+1])=

(q,a)。(但是，時間復(fù)雜度高)KMP算法的思路是：第一步，如果有P[q+1]=T[i+1]，那么顯然有

(T[1..i+1])=q+1，否則做第二步。第二步，如果T[i+1]=a

但是P[q+1]=b，a

b，我們把模式P向右滑動去找下一個與T[1..i+1]的后綴，也就是Pqa的后綴，相匹配的P的最大前綴。這個前綴必定要小于q+1。所以，這一步找出小于q+1的Pqa的后綴函數(shù)，即

(Pqa,q+1)，就是解。27如何找小于q+1的Pqa的后綴函數(shù)？如果Pk+1與Pqa的后綴相匹配，那么Pk必定與Pq

的后綴相匹配，且必有k<q。所以，我們先要找的是小于q的Pq

的后綴函數(shù)

(Pq,q)。定義13.7設(shè)Pq(1

q

m)是模式P[1..m]的一個前綴。Pq的前綴函數(shù)

[q]定義為

[q]=

(Pq,q)，也就是小于

q的

Pq的后綴函數(shù)。有了

[q](1

q

m)后，KMP計算

(Pqa,q+1)的步驟如下。計算Pqa的后綴函數(shù)算法

設(shè)

[q]=k，k=

(Pq,q)，k<q。如果P[k+1]=T[i+1]，那么Pk+1

就是小于(q+1)的與Pqa的后綴匹配的最大前綴。所以，k+1=

(Pqa,q+1)=

(T[1..i+1])。否則，P[k+1]=c

a。這時，我們需要繼續(xù)把P向右滑動去找下一個與Pq

的后綴相匹配的前綴Pk’。（接下頁）28計算Pqa的后綴函數(shù)算法（繼續(xù)）因為

Pk是Pq的后綴，k’<k，所以下一個與Pq

的后綴相匹配的前綴Pk’

也就是與Pk后綴匹配的最大前綴，k’是

Pk的前綴函數(shù)，k’=

[k]。找到前綴Pk’

后，重復(fù)上面的做法，即檢查是否有P[k’+1]=a。如果是，則有

(T[1..i+1])=k’+1。否則，再重復(fù)這個做法，找Pk’的前綴函數(shù)k’’=

[k’]，直至成功。下圖(13-7)給出了一個例子。29圖13-7用前綴函數(shù)找T[i+1]的后綴函數(shù)的例子給定一個模式P[1..m]后，它的前綴函數(shù)可以用下面的算法計算。30Prefix-Function(P[1..m])

[1]

0 //P1的前綴函數(shù)為0，即P1的前綴函數(shù)為空k

0 //k是P[1]的前綴函數(shù)for

q

2to

m //計算

[q]

while

k>0and

P[k+1]

P[q] //k是

[q-1]，下面算

[q] k

[k]endwhileifP[k+1]=P[q]

then

k

k+1endif

[q]

kendfor

return

End31i123456789P[i]abcababca

[i]000121234例13.7假設(shè)有字符集

={a,b,c}和模式P=abcababca，計算P的前綴函數(shù)。引理13.1 算法Prefix-Function正確地計算模式P的前綴函數(shù)。證明：算法初始化

[1]=0后，用一個for循環(huán)逐個計算

[q](2

q

m)。這里，q是循環(huán)變量。用歸納法證明這個循環(huán)算法正確。斷言：

每輪循環(huán)前，

[q-1]是Pq-1的前綴函數(shù)；

循環(huán)結(jié)束時，

[q]是Pq的前綴函數(shù)。初始化：在for循環(huán)前，

[1]=0。因為小于P1的前綴只能是P0，所以

[1]=0是正確的，因為第一輪q

=2，滿足斷言，即

[q-1]是Pq-1的前綴函數(shù)。32引理13.1 證明(繼續(xù)1)循環(huán)維持：假設(shè)某輪的循環(huán)變量是q，設(shè)開始前，

[1],

[2],…,

[q-1]已正確計算。現(xiàn)在證明，這一輪完成時，

[q]的計算也是正確的。注意到，如果

k+1=

[q]，那么，k必須滿足兩個必要條件：(1)Pk是Pq-1的后綴，k<q-1，(2)P[k+1]=P[q]。滿足兩個條件的所有前綴Pk+1中，最長的一個的長度k+1就是

[q]。設(shè)

[q-1]=k，Pk是滿足第(1)條件的最大的前綴。算法Prefix-Function的做法是，從k=

[q-1]開始，從大到小，檢查每一個滿足第(1)條件的前綴Pk是否也滿足第(2)條件。在檢查過程中，第一個滿足兩個條件的，顯然就是解。例如，k=

[q-1]。這時，如果有P[k+1]=P[q]，滿足第(2)條件，那么如下圖(13-9)所示，顯然有

[q]=k+1。33引理13.1 證明(繼續(xù)2)：為了減少搜索時間，當(dāng)P[q]

P[k+1]時，k不滿足第(2)條件，我們要跳過那些肯定不滿足第(1)條件的k’。因為Pk是Pq-1的后綴，那么下一個滿足第(1)條件的

k’一定是Pk的前綴函數(shù)k’=

[k]。因為k<q，由歸納假設(shè)，

(k)已經(jīng)正確地算好。下圖(13-10)顯示了這個關(guān)系。34這時，如果有P[q]=P[k’+1]，那么

[q]=k’+1。否則，下一個滿足第(1)條件的k’’一定是Pk’

的前綴函數(shù)k’’=

[k’]。這時，如果P[q]=P[k’’+1]，那么

[q]=k’’+1，否則再繼續(xù)這個過程。算法的第4行的while循環(huán)就是做的這件事。(接下頁)P[q]q-1

P[k+1]kP[k’+1]k’k=

(q-1)k’=

(k)引理13.1 證明(繼續(xù)3)：35引理13.1 證明(繼續(xù)4)當(dāng)while循環(huán)結(jié)束時，要么k=0，要么P[k+1]=P[q]。如果k=0，表示沒有前綴最能滿足第(2)條件，顯然有

[q]=k=0。否則，

[q]=k+1正確。算法第8行只改變后者的

k為

k+1，使得第10行正確地輸出結(jié)果。所以，這一輪的前綴函數(shù)

(q)計算正確。循環(huán)終止：因為每次while循環(huán)的時間是O(m)，所以每次for循環(huán)的時間是O(m)。因為for循環(huán)一共n次，所以循環(huán)會終止。歸納成功。

算法的時間復(fù)雜度是O(m)。這是因為，變量

k在第8行被加1，一共加了最多(m-1)次，總共增加的值最多是(m-1)。因為

k的值始終是非負整數(shù)，所以k

被減少的次數(shù)最多是(m-1)次，因此第4行的while循環(huán)總共被執(zhí)行了最多(m-1)次。所以算法的時間復(fù)雜度是O(m)。有了前綴函數(shù)后，KMP算法如下。36KMP-Matcher(T[1..n],P[1..m])

[1..m]

Compute-Prefix-Function(P[1..m]) //先算前綴函數(shù)q

0 //已匹配的字符個數(shù)為qfor

i

1ton //從左到右掃描每個字符 whileq>0and

P[q+1]

T[i] //已知Pq=T[i-q..i-1]

q

[q] //滑動P到下個與Pq后綴相配位置

endwhile

ifP[q+1]=T[i] //不論q=0或q>0

then

q

q+1 //已匹配的字符個數(shù)為q+1

endif //否則沒有字符與T[1..i]后綴匹配，q=0

ifq=m //模式得到匹配，輸出這個合法移位

then print“Patternoccurswithshift”i-m

q

[q] //更新為q的前綴函數(shù)

endif

endfor //對T[i]的掃描完成。End37KMP-Matcher的復(fù)雜度分析算法的第一步計算前綴函數(shù)，需要O(m)時間。其后，主要部分是第3行的for循環(huán)。每次循環(huán)，算法可能做三件事：如果P[q+1]

T[i]，向右滑動P到下個可能相配位置，變量q減小。如果P[q+1]=T[i]，變量q加1。如果q=m，則報告合法位移。因為合法移位的個數(shù)≤n–m+1，做第3件事的時間為O(n)。因為每做一次第2件事，變量i就會加1，而變量i最多等于n，所以，做第2件事的次數(shù)小于等于n。最后，因為每做一次第1件事，變量q至少會減1，由于q的初值為0，而且始終不為負值，所以q被減少的次數(shù)不會超過q被增加的次數(shù)。又因為q被增加的唯一原因是算法做了第2件事，所以q被增加的次數(shù)小于等于n。所以，算法做第1件事的次數(shù)也不會大于n。所以，KMP-Matcher的復(fù)雜度為O(m)+

O(n)=O(n)。38例13.8以模式P=abaab和文本T=ababaababaaabaab為例解釋KMP算法。解： KMP算法先計算P的每個前綴的前綴函數(shù)如下表所列。i12345P[i]abaab

[i]00112基于這個前綴表，下面表格計算出到文本每一字符為止，變量q值。在計算中，一個字符的q值可能須要查找前綴表多次，表中列出這一過程。例如，i=12時，第一次找到前綴k=1,然后k’=0。i初始12345678910111213141516T[i]--ababaababaaabaab前面前綴q

1

21

1,0

最終前綴q01232345323412345更新后q

2

2合法移位--------------2----------------1139KMP-Matcher的正確性證明定理13.2給定T[1..n]和P[1..m]，KMP-Matcher正確地算出所有合法移位。證明：我們證明它實際上是基于自動機的算法的另一種實現(xiàn)。兩個算法都是逐字掃描字符T[i](1

i

n)并計算T[1..i]的后綴函數(shù)

(T[1..i])。一旦有

(T[1..i])=m，則發(fā)現(xiàn)一個合法移位。KMP算法第一步是計算前綴函數(shù)以便掃描字符時用，已證明正確。初始時，變量i=1，