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

1第13章 字符串匹配字符串匹配的定义 2一个朴素的字符串匹配算法 4Rabin-Karp算法 5基于有限状态自动机的匹配算法 11Knuth-Morris-Pratt(KMP)算法 24

1.字符串匹配的定义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?0ton-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很大时不可能