计算机算法基础 第2版 课件 第13章 字符串匹配

1第13

章

字符串匹配字符串匹配的定义

2

一个朴素的字符串匹配算法

4Rabin-Karp算法

5基于有限状态自动机的匹配算法

11Knuth-Morris-Pratt(KMP)算法

241.字符串匹配的定义2许多应用问题需要确定一个给定的模式是否在一个文本中出现，并找出这个模式在文本中所有出现的位置。例如，在编辑文章时，我们希望找出一个单词出现的所有地方。文本(text)：

是一个有序的符号序列，符号取自一个给定的符号集合

。例如，

={0，1}，那么，一个文本就是一个只含0和1的字符串。通常我们用数组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这个朴素的算法有较高的复杂度O(m(n-m))。2.一个朴素的字符串匹配算法TPs=3abaacabaabcabacbas=1s=2s=0例13.1s=3是合法移位5为简单起见，先用

={0,1,...,9}为例来解释。主要思路是：把P[1..m]看作一个m位的十进制数字，并假设它的值是p。移位s的字符段Ts

=T[s+1..s+m]也视为有m位的一个十进制数字，并假设它的数值是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，我们把

中符号与0到d-1

的d个数字，0,1,2,…,d-1，建立一一对应关系，那么P[1..m]则对应一个m位的d进制数p。3.Rabin-Karp算法6当

是任意集合时，|

|=d，这时Horner公式为：p=P[m]+d(P[m-1]+d(P[m-2]+…+d(P[2]+dP[1])…)) (13.1)例13.2 假设

是26个英语字母的集合，我们把字母从a到z顺序对应到数字0到25，请计算P[1..4]=dfaz对应的数值p。解：

因为字母d对应于3，f对应于5，a对应于0，z对应于25，所以有： p=25+26(0+26(5+26

3))=56133。

显然，计算P[1..m]的值只需O(m)时间。计算ts

的值显然，计算t0

的值也只需O(m)时间。而得到t0

之后，计算t1只需要常数时间就可以了。具体公式为：

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

的值(继续)所以，从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)时，每一步的算术操作必须能在常数时间内完成。这个要求在m和n很大时不可能，因为乗积会很大，远大于计算机一个存储单元的容量。解决方法：我们选一个合适的质数q作模数，使所有的运算都是在模q下进行。这样一来，所有算术运算的结果值都不超过q。我们选质数q使得乘积dq可以存放在计算机一个单元内。同时，上面的迭代公式(13.1)和(13.2)也相应地修改为：

(见下页)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，可预先在O(m)时间内算好。p=P[1..m]和t0=T[1..m]也可在O(m)时间内先算好。算出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

不一定导致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

//匹配前预处理，计算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(继续)for

s

0to

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

P[1..m]=T[s+1..s+m] //检查真伪

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))时间做匹配检查。所以，它的最坏情况复杂度是O(m(n-m))。但是，如果合法移位的个数是常数，那么算法的复杂度为O(n)。114.基于有限状态自动机的匹配算法有限状态自动机简介一个有限状态自动机(finitestateautomaton,FSA)M是一个

5元组(Q,q0,A,

,

)，其中，Q

一个有限个状态的集合；q0

是Q中的一个状态，q0

Q，被指定为初始状态；A

是Q的一个子集，A

Q，它的状态被指定为接收状态；

有限个输入符号的集合；

状态转换函数

:Q

Q。12自动机M对字符串w进行识别的算法M一开始是在初始状态q0。然后，按照串w中字符顺序，逐个字符扫描。如果它的当前状态，即扫描某个字符a之前的状态是q，那么它扫描字符a后进入的状态由状态转换函数决定。

如果

(q，a)=q’，那么自动机M

进入状态q’。

这里，q’是Q中另一个状态，也可能q’=q，状态不变。串w中每个字符都被扫描后自动机M进入的状态称终止状态。如果终止状态是一个接收状态，那么我们说自动机M接收字符串w，否则拒绝w。如果在扫描过程中某一步，自动机M进入了一个接收状态，那么我们说自动机M接收当前已被扫描过的字符形成的字符串。13例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}。请判断M是否接收w=abba。解：转换函数

可以用一个表格表示：

输入符号状态ab010100从q0开始，自动机对w=abba逐字扫描后的状态顺序为：q0=0,

(0,a)=1,

(1,b)=0,

(0,b)=0,

(0,a)=1。所以M接收w=abba。可简化为：

(q0,w)=

(0,abba)=

(1,bba)=

(0,ba)=

(0,a)=1。14一些有关概念和术语由字符集

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

在内，的集合称为全语言并记为

*。自动机M实际上定义了一个从

*到状态集合Q的函数

:

*

Q，称为最终状态函数:

给定w

*，如果w=

，那么

(

)=q0，否则

(w)=

(q0,w)。即，w的最终状态函数值就是M扫描w后的终止状态。自动机M可以等价地用一个有向图表示。图中每一个点(小圆圈)对应于一个状态、如果有

(u,a)=v，则有一条标号为a的边(u,v)。另外，用一个箭头(不计入图的边)指向对应于初始状态q0的顶点，而对每一个接收状态对应的顶点用双层圆圈标出。15例: 对应于例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}。

输入符号状态ab01010016

17字符串匹配用的自动机的构造给定

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

,

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

(q,a)=

(Pqa)，这里a是

中任一字符。基本思路：从T[1]开始，逐字扫描T[i]。如果

(T[1..i])=q，那么进入状态q。如果s是合法移位，那么在扫描T[s+m]后会进入状态m而被发现。假设扫描T[1..i]后的状态是q，即

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

(Pqa)。(见下图)18图13-419例13.5假设有字符集

={a,b,c}和模式P=abca，请用有向图描述用于匹配该模式的有限状态自动机。解：下图(13-5)中有向图表示了这个自动机，它的转换函数是由直接观察得到的。a0123cbaaab,c4cbbcab,c给定字符集

和模式P[1..m]后，构造自动机的工作主要是计算状态转換函数

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

21基于有限状态自动机的串匹配算法构造好一个用于匹配的有限状态自动机以后，文本串中所有合法移位可由下面算法找到。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)时间。如果加上构造自动机的时间，总的复杂度是O(n+m3|

|)。22例13.6假设有字符集

={a,b,c}和模式P=abca，请解释算法Finite-Automaton-Matcher是如何用有限状态自动机找出文本T=cabcabcab的所有合法移位的。解：这个模式对应的自动机已由图13-5给出。这题的文本串有9个字母。下图(13-6)列出了上面算法(第3行)用自动机的状态函数扫描每个字符T[i]，i=1,2,…,9,后所得的状态q值。算法在扫描字符T[4]和T[7]后发现两处成功匹配，其合法移位分别是1和4。(见下页)23a0123cbaaab,c4cbbcab,ci开始前123456789T[i]

cabcabcab状态q0012342342合法移位----------1----4--245.Knuth-Morris-Pratt(KMP)算法和基于自动机的算法相似，也是逐字扫描T[i]并计算T[1..i]的后缀函数

(T[1..i])。如果发现

(T[1..i])=m，则发现一个合法移位。KMP不预先计算转換函数。扫描T[i]后，不能立即得到

(T[1..i])。而是要临时计算。KMP也需要预处理，但不是计算转換函数

，而是计算“前缀函数”

[1..m]，并且只需要O(m)时间。前缀函数

[1..m]帮助KMP，在扫描T[i]后，快速地实时地计算

(T[1..i])。KMP扫描字符T[i]时，虽然要多化些时间去临时计算

(T[1..i])，但保证总的匹配时间仍是线性时间O(n)，并省去了费时的预处理时间。25

26答案：因为

(T[1..i])=q，T[i+1]=a，那么T[1..i+1]的后缀函数也就是Pqa的后缀函数

(Pqa)。基于自动机的算法的做法是：预先算好Pqa的后缀函数，

即转换函数

(q,a)，可立即得到

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

(q,a)。(但是，时间复杂度高)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的后缀函数，即

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

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

的后缀函数

(Pq,q)。定义13.7设Pq(1

q

m)是模式P[1..m]的一个前缀。Pq的前缀函数

[q]定义为

[q]=

(Pq,q)，也就是小于

q的

Pq的后缀函数。有了

[q](1

q

m)后，KMP计算

(Pqa,q+1)的步骤如下。计算Pqa的后缀函数算法

设

[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。这时，我们需要继续把P向右滑动去找下一个与Pq

的后缀相匹配的前缀Pk’。（接下页）28计算Pqa的后缀函数算法（继续）因为

Pk是Pq的后缀，k’<k，所以下一个与Pq

的后缀相匹配的前缀Pk’

也就是与Pk后缀匹配的最大前缀，k’是

Pk的前缀函数，k’=

[k]。找到前缀Pk’

后，重复上面的做法，即检查是否有P[k’+1]=a。如果是，则有

(T[1..i+1])=k’+1。否则，再重复这个做法，找Pk’的前缀函数k’’=

[k’]，直至成功。下图(13-7)给出了一个例子。29图13-7用前缀函数找T[i+1]的后缀函数的例子给定一个模式P[1..m]后，它的前缀函数可以用下面的算法计算。30Prefix-Function(P[1..m])

[1]

0 //P1的前缀函数为0，即P1的前缀函数为空k

0 //k是P[1]的前缀函数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假设有字符集

={a,b,c}和模式P=abcababca，计算P的前缀函数。引理13.1 算法Prefix-Function正确地计算模式P的前缀函数。证明：算法初始化

[1]=0后，用一个for循环逐个计算

[q](2

q

m)。这里，q是循环变量。用归纳法证明这个循环算法正确。断言：

每轮循环前，

[q-1]是Pq-1的前缀函数；

循环结束时，

[q]是Pq的前缀函数。初始化：在for循环前，

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

[1]=0是正确的，因为第一轮q

=2，满足断言，即

[q-1]是Pq-1的前缀函数。32引理13.1 证明(继续1)循环维持：假设某轮的循环变量是q，设开始前，

[1],

[2],…,

[q-1]已正确计算。现在证明，这一轮完成时，

[q]的计算也是正确的。注意到，如果

k+1=

[q]，那么，k必须满足两个必要条件：(1)Pk是Pq-1的后缀，k<q-1，(2)P[k+1]=P[q]。满足两个条件的所有前缀Pk+1中，最长的一个的长度k+1就是

[q]。设

[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 证明(继续2)：为了减少搜索时间，当P[q]

P[k+1]时，k不满足第(2)条件，我们要跳过那些肯定不满足第(1)条件的k’。因为Pk是Pq-1的后缀，那么下一个满足第(1)条件的

k’一定是Pk的前缀函数k’=

[k]。因为k<q，由归纳假设，

(k)已经正确地算好。下图(13-10)显示了这个关系。34这时，如果有P[q]=P[k’+1]，那么

[q]=k’+1。否则，下一个满足第(1)条件的k’’一定是Pk’

的前缀函数k’’=

[k’]。这时，如果P[q]=P[k’’+1]，那么

[q]=k’’+1，否则再继续这个过程。算法的第4行的while循环就是做的这件事。(接下页)P[q]q-1

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

(q-1)k’=

(k)引理13.1 证明(继续3)：35引理13.1 证明(继续4)当while循环结束时，要么k=0，要么P[k+1]=P[q]。如果k=0，表示没有前缀最能满足第(2)条件，显然有

[q]=k=0。否则，

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

k为

k+1，使得第10行正确地输出结果。所以，这一轮的前缀函数

(q)计算正确。循环终止：因为每次while循环的时间是O(m)，所以每次for循环的时间是O(m)。因为for循环一共n次，所以循环会终止。归纳成功。

算法的时间复杂度是O(m)。这是因为，变量

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

k的值始终是非负整数，所以k

被减少的次数最多是(m-1)次，因此第4行的while循环总共被执行了最多(m-1)次。所以算法的时间复杂度是O(m)。有了前缀函数后，KMP算法如下。36KMP-Matcher(T[1..n],P[1..m])

[1..m]

Compute-Prefix-Function(P[1..m]) //先算前缀函数q

0 //已匹配的字符个数为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 //已匹配的字符个数为q+1

endif //否则没有字符与T[1..i]后缀匹配，q=0

ifq=m //模式得到匹配，输出这个合法移位

then print“Patternoccurswithshift”i-m

q

[q] //更新为q的前缀函数

endif

endfor //对T[i]的扫描完成。End37KMP-Matcher的复杂度分析算法的第一步计算前缀函数，需要O(m)时间。其后，主要部分是第3行的for循环。每次循环，算法可能做三件事：如果P[q+1]

T[i]，向右滑动P到下个可能相配位置，变量q减小。如果P[q+1]=T[i]，变量q加1。如果q=m，则报告合法位移。因为合法移位的个数≤n–m+1，做第3件事的时间为O(n)。因为每做一次第2件事，变量i就会加1，而变量i最多等于n，所以，做第2件事的次数小于等于n。最后，因为每做一次第1件事，变量q至少会减1，由于q的初值为0，而且始终不为负值，所以q被减少的次数不会超过q被增加的次数。又因为q被增加的唯一原因是算法做了第2件事，所以q被增加的次数小于等于n。所以，算法做第1件事的次数也不会大于n。所以，KMP-Matcher的复杂度为O(m)+

O(n)=O(n)。38例13.8以模式P=abaab和文本T=ababaababaaabaab为例解释KMP算法。解： KMP算法先计算P的每个前缀的前缀函数如下表所列。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正确地算出所有合法移位。证明：我们证明它实际上是基于自动机的算法的另一种实现。两个算法都是逐字扫描字符T[i](1

i

n)并计算T[1..i]的后缀函数

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

(T[1..i])=m，则发现一个合法移位。KMP算法第一步是计算前缀函数以便扫描字符时用，已证明正确。初始时，变量i=1，