2010-5-14 计算机算法设计与分析 1
第七章
字符串
2010-5-14 计算机算法设计与分析 2
字符串的概念
? 字符串是由零个或多个字符组成的有限
序列集合，通常我们把字符串简称为串。
? 在高级语言中一般都是用引号（“）或
单引号（’）括起来，例如，串 a1a2… an,，
我们一般记为,a1a2… an,”或‘ a1a2… an,’。
2010-5-14 计算机算法设计与分析 3
串的几个概念
? 1、长度：串 s中字符的个数，记为 length(s) 。
长度为 0的串称为空串。
? 2、子串：串中的连续字符序列。而包含子串
的串称为主串。定义空串是任意串的子串。
? 3、位置：字符的位置是它在串中的序号；子
串的位置是它的首字符的位置。
? 4、串相等：两个串相等当且仅当它们完全一
致，即长度和对应位置上的字符都相同。
2010-5-14 计算机算法设计与分析 4
串的匹配
? 给定长度为 n的串 T = t1t2……t n (T称为正
文 )，以及另一个串 P = p1p2……p m (P称为
模式 )，查找模式 P在正文 T中首次出现或
所有出现的位置的过程称为模式匹配 。
2010-5-14 计算机算法设计与分析 5
简单的串模式匹配算法
? 将模式 P看成关键字，从正文 T的第 1个元
素开始，
? 逐个与 T中的 P[0]个元素比较；
? 如果这个长度为 P[0]的子串与模式 P相等，
则匹配成功；否则，又从 T的第 2个元素
开始进行同样的比较。
? 如此继续 T[0] – P[0] + 1步。
2010-5-14 计算机算法设计与分析 6
简单的模式匹配算法
? int StrMatch(SString S,SString P)｛
? i = 1； j = 1；
? while(i <= S[0] && j <= P[0])｛
? if (S[i] == P[j])｛ i++; j++;｝
? else {i = i – j + 2； j = 1}
? ｝
? if(j > P[0]) return i – P[0]；
? return 0;
? ｝
2010-5-14 计算机算法设计与分析 7
简单的模式匹配算法的评估
? 在回朔深度不大的情况下，模式匹配算
法的时间复杂度为 O(m+n)
? 在最坏情况下的时间复杂度为 O(n*m)。
2010-5-14 计算机算法设计与分析 8
KMP算法
? KMP算法是 D,Knuth与 V,Pratt和 J,Morris同时
发现的，故称为 Knuth_Morris_Pratt算法。
? 其思想是：每当匹配过程中出现字符不等时，
不是简单地从正文的下一个字符 (即 i+1)开始重
新比较，而是利用已经得到的“部分匹配”的
结果将模式串向右“滑动”尽可能远的一段距
离后，再进行比较。
? KMP算法的时间复杂度为 O(n+m)。
2010-5-14 计算机算法设计与分析 9
能向右滑动多远？
p1 … p k … p j … p m
s1 …… s i …… s n
当 si ? pj,就将模式向右移动。假设 pk和 si相比较：
s1 …… s i …… s n
p1 … p k … p j … p m
显然应有,si–k+1…s i–1 = p1…p k–1。
s …
…
而由前次的比较应有,si–k+1…s i–1 = j–k+1 …p j–1。
于是得到这样的结果：
p1…p k–1 = pj–k+1 …p j–1。
2010-5-14 计算机算法设计与分析 10
滑动的距离只取决于模式
? 模式滑动距离只取决于模式本身，与正文无关 。
? 设函数 next[j]为当模式中第 j个字符与正文中相
应字符“失配”时，在模式中需重新和正文中
该字符进行比较的字符的位置。
0 当 j=1时
? next[j] = max {k |1<k<j且 p1…p k–1= pj–k+1…p j–1}
1 当不存在相应的 k时
2010-5-14 计算机算法设计与分析 11
一个模式的 next(j)
? j, 1 2 3 4 5 6 7 8 9
? 模式, a b a a b a a a b
? next[j],
初始化,next[1] = 0。
0
没有相应的 k,next(j)为 1。
1 1
k = 2,下次从第二个元素开始比较。
2 2
依次以此类推可得其余元素的 next(j)。
3 4 5 2
2010-5-14 计算机算法设计与分析 12
滑动不会造成遗漏
? KMP算法不再是将正文依次和模式中的
元素逐个地进行匹配，而是当出现“失
配”时从模式的第 k(k=next(j))个元素开
始重新比较，这样会不会遗漏掉可以匹
配的子串呢？
? 不会的。因为滑动的距离 next(j)被定义为
满足 p1…p k–1= pj–k+1…p j–1的最大的 k。
2010-5-14 计算机算法设计与分析 13
滑动不会造成遗漏
? 引理 7.1,正文 S和模式 P比较时，若 si≠pj,则
S没有以 si–k0+1(next[j]<k0<i)开头的子串匹配 P。
? 证明：当 next[j]=0或 1时，结论显然成立。
? 当 next[j]>1时，假设结论不成立，即存在这样
的 k0,那么有 p1 p2 …p k0–1= si–k0+1si–k0+2 …s i–1。
? 从而有,p1 p2 …p k0–1= pj–k0+1pj–k0+2 …p j–1 (7.3)
? 由假设有 next[j]<k0<i。 这与 next[j]是满足 (7.3)
式的最大值相矛盾；所以结论成立。
2010-5-14 计算机算法设计与分析 14
KMP模式匹配算法
? int next[MaxStrLen]; //已算好的模式的 next值
? int KMP_StrMatch(SString S,SString P)｛
? int i = 1,j = 1,m = 0;
? while(i <= S[0] && j <= P[0])
? if (j = 0 || S[i] = P[j])｛ i++; j++;｝
? else j = next[j]; //失配时从 next[j]重新比较
? if(j > P[0]) m = i – j + 1;
? return(m);
? ｝
2010-5-14 计算机算法设计与分析 15
next(j)的计算
? 如何来计算模式 P的 next(j)?
? 首先，我们由定义可知 next(1) = 0；
? 其次，显然有 next(2) = 1；
? 现在我们来考虑 next(j+1)。
? 由 next(j)=k可知模式中有,p1…p k–1= pj–k+1…p j–1。
? 现在存在两种情况,pk = pj或者 pk ? pj。
? ⑴ 如果 pk = pj,于是 p1… p k–1pk= pj–k+1… p j–1pj。
从而有 next(j+1) = next(j) +1。
2010-5-14 计算机算法设计与分析 16
next(j)的计算
? ⑵ 如果 pk ? pj,显然 next(j+1) ? next(j)。
? 这实际是在将 p1… p k–1pk与 pj–k’+1… p j–1pj相匹配
时，出现了 pj与 pk失佩 。
p1 … p k–1 pk pj–k+1 … p j–k+1 pj ……
p1 … p k–1 pk pk ? pj
? 下一步拿 p1… p k–1pk中哪个元素和 pj相比较呢？
滑动多远？? 向右滑动 next(k),即比较 pnext(k)和 pj。
? 若这时有 pnext(k) = pj,则 next(j+1) = next(k) + 1；
? 若这时有 pnext(k) ? pj,则再重复以上的做法，
直至 k = 1。
2010-5-14 计算机算法设计与分析 17
next(j)的计算
? int next[MaxStrLen];
? void get_next(SString P) {
? j = 1; next[1] = 0; k = 0；
? while(j <= P[0])
? if (k == 0‖ P[k] = P[j])
? {++k; ++j; next[j] = k;}//next(j+1)=k +1
? else k = next[k]; }
初始化
循环逐个计算元素 j的 next(j)若 pk = pj,则 next(j+1)=k +1。
注意此处的 k,j都加了 1。
若 pk ? pj,则 比较 pnext(k)和 pj
2010-5-14 计算机算法设计与分析 18
一个模式的 next(j)
? j, 1 2 3 4 5 6 7 8 9
? 模式, a b a a b a a a b
? next[j],
初始化,j = 1; next[1] = 0; k = 0；
10
第一趟,j ; k = 0；
∵ k = 0
∴ {++k; ++j; next[j] = k;}
即,k = 1; j = 2; next(2) =1。
第二趟,j = 2; k =
∵ P[1] ? P[2]
∴ k = next[k] = 0
∵ k = 0
∴ {++k; ++j; next[j] = k;}
即,k = 1; j = 3; next(3) =1。
1
第三趟,3 。
∵ ] = P[3]
∴ ; j; t[j] ;}
即,2; j 4; t(4) 2。
2
第四趟,4 k = 2。
∵ 2 4
∴ t[2 1
∵ // k = 1
∴
即,5 5 。
2
第五趟,5 。
∵ P[2 5
∴
即,3 6 6 3。
3
第六趟,6 3。
∵ 3 6
∴
4 7 7 4。
4
第七趟,7 4。
∵ 4 7
∴
5 8 8 5。
5
第八趟,8 5。
∵ 5 ? 8
∴ k next[k] = next[5] = 2。
∵
∴ 2 1。
∵ 1 //
∴
即,9 9 2
2
至此循环结
束，求出了
所有元素的
next(j)。
2010-5-14 计算机算法设计与分析 19
Boyer-Moore算法
? Boyer-Moore串匹配算法 (简称 BM算法 )。
? 其思想是在匹配过程中，一旦发现在正
文中出现模式中没有的字符时就可以将
模式、正文大幅度地“滑过”一段距离。
? 同时考虑到多数不匹配的情形是发生在
最后的若干个字符，采用从左到右的方
式扫描将浪费很多时间，因此改自右到
左的方式扫描模式和正文，
2010-5-14 计算机算法设计与分析 20
Boyer-Moore算法
s1 …… s i …… s n
p1 … p j … p m
? 令 si = c。 如果在 pj和 pm之间没有符号 c的话，即
pj = c且是 j最大的, 就可以将模式右移 m – j个
元素，再与模式 P来进行比较。
p1 p j … p m 移到 si+m–j再来比较
? 如果符号 c是模式中没有的符号，就可以将模
式右移 m 个元素后，再与模式 P来进行比较。
2010-5-14 计算机算法设计与分析 21
滑动距离函数 dist(c)
? 为此,对给定的模式 P=p1p2…… pm,定义
从正文字母集 C到正整数的函数：
dist:C?{1,2,……,m}
为：
m c?P,或 c= pm且 c? pj(0<j<m)
? dist(c) =
m – j 否则 (j=max{c= pj,0<j<m)
2010-5-14 计算机算法设计与分析 22
BM串匹配算法
? int BM_string_Matching(char *s,char *p){
? int i,j,m,n;
? m=p[0]; n=s[0]; i=m;
? while(i<=n){
? j = m; k = i;
? while(j>0 && p[j] == s[k]){
? j--; k--;}
? if(j==0) return(i-m+1);
? else i+=dist[s[k]]; }
初始化从左至右循环匹配模式 P
从右至左循环比较每个符号
若 j = 0,则匹配成功，否则
将模式右移 dist[s[k]]。
2010-5-14 计算机算法设计与分析 23
函数 dist(c)的计算
? Void Computer_Distance(char *P){
? int i,j,m;
? m = P[0];
? for(i = 0; i < 256; i++)
? dist[i] = m;
? for(j = m –1; j > 1; j ––)
? if(dist[P[j]] = = m)
? dist[P[j]] = m – j;
? }
先令每一个符号的 dist(i) = m
对模式 P中符号的 dist进行修改
2010-5-14 计算机算法设计与分析 24
BM算法评估
? Computer_Distance函数的时间复杂度为
Θ(m)，
? 在最坏的情形下 BM算法的每次内循环次
数为 m,所以 BM算法最坏时间复杂度为
Θ(mn)。
2010-5-14 计算机算法设计与分析 25
KARP-RABIN串匹配随机算法
? 1987年 KARP和 RABIN教授发表了一种简单快
速的串匹配随机算法（简称 KR算法）。
? 基本思想是：先将模式和正文的每个长度为 m
的子串映都射成对应的整数值 (指印 )。完成这
个映射的函数称为指印函数。
? 然后对与模式具有相同指印的子串进行比较。
? 算法的主要时间是指印的计算和整数的搜索，
所以能够 达到快速匹配的目的。
2010-5-14 计算机算法设计与分析 26
,指印, 函数的定义
? 设模式 P为 p1p2…p m,正文 T为 t1t2…… tn,正文
和模式中出现的字符集合为 ?,且 | ? | = d。
? 对 ?上的 长度 m的符号串 ? = t1t2…t m,令整数
x = asc(t1)dm–1+ asc(t2)dm–1+…+ asc(t m)，
? 则符号串 ?的指印函数 K(?)为
K(?) = x mod q
? 这里 asc(c)为字符 c的 ASCII值,q是 [1,n2m]中随
机选取的适当大的素数。
2010-5-14 计算机算法设计与分析 27
KARP-RABIN算法的基本思路
? 首先计算模式，以及正文中所有长度为 m
的子串的指印函数。
? 然后匹配与模式串指印函数值相等的正
文中的子串，找到匹配串。
2010-5-14 计算机算法设计与分析 28
指印函数的递归计算
? 令 titi+1……t i+m–1的对应的整数为，
? yi = asc(ti)dm–1+ asc(ti+1)dm–2+…+ asc(t i+m–1)，
? 则 ti+1ti+2……t i+m的对应的整数为
? yi+1 = asc(ti+1)dm–1 +… +asc(ti+m–1)d+asc(ti+m)(yi – asc(ti)dm–1)d + asc(ti+m
? 因此，
?K(yi+1) = (yi – asc(ti)dm–1)d+asc(ti+m) mod qK(yi) – asc(ti)z) + asc(ti+m) mod q
? 其中,z = dm–1 mod q。
2010-5-14 计算机算法设计与分析 29
KARP-RABIN串模式匹配算法
? int K-RMatch(char *t,int n,char *p,int m){
? 数据说明；
? 计算指印函数计算中的 z;
? 计算模式 p和正文第一个子串的指印；
? 依据指印逐个匹配正文的子串； }
int i,j,k,z = 1,x = 0,y = 0;
for(i = 1; i < m; i++) z=(z*d) mod q;
这里 d是正文和模式中符号的个数,q是事先
随机选取的适当的素数。它们都是全局变量。
for(i = 1; i <= m; i++){
x = (x * d + asc(p[i])) mod q;
? y = (y * d + asc(t[i])) mod q;}
? 依据指印逐个匹配正文的子串； }
2010-5-14 计算机算法设计与分析 30
依据指印逐个匹配正文子串
? i = 1;
? while(i <= n – m){
? if(x == y){ k = 1; j = i;
? while(t[j] = p[k] && k <= m){j++; k++; }
? if(k > m) return(i)
? if(i <= n – m){
? y = ((y – z * t[i])*d + t[i + m]) mod q;
? i++;}
? return(0);}}}
从第一个子串开始循环逐个进行匹配。 若子串与模式的指印相同，
对其符号逐个进行比较。
匹配成功返
回其位置。
匹配不成功，计算下个
子串的指印，继续循环。
2010-5-14 计算机算法设计与分析 31
KARP_RABIN算法 的评估
? 不考虑子串匹配，时间复杂度为 O(n+m)。
? 考虑子串匹配，最差时间复杂度为 O(nm)。
? 只要选择的素数相当大，指印冲突几乎
没有，因而实际运行时间为 O(n+m)。
? 此算法很容易推广到二维情形，便于进
行算法的并行化，被广泛使用于计算机
图形处理领域。
2010-5-14 计算机算法设计与分析 32
小结
? 本章介绍了几种常用的符号串匹配算法：
Knuth_Morris_Pratt算法,Boyer-Moore算
法,Karp-Rabin随机算法。
? 这些算法的时间复杂度都是 O(n+m),最
差情况为 O(n*m)。
2010-5-14 计算机算法设计与分析 33
2010-5-14 计算机算法设计与分析 34
第七章
字符串
2010-5-14 计算机算法设计与分析 2
字符串的概念
? 字符串是由零个或多个字符组成的有限
序列集合，通常我们把字符串简称为串。
? 在高级语言中一般都是用引号（“）或
单引号（’）括起来，例如，串 a1a2… an,，
我们一般记为,a1a2… an,”或‘ a1a2… an,’。
2010-5-14 计算机算法设计与分析 3
串的几个概念
? 1、长度：串 s中字符的个数，记为 length(s) 。
长度为 0的串称为空串。
? 2、子串：串中的连续字符序列。而包含子串
的串称为主串。定义空串是任意串的子串。
? 3、位置：字符的位置是它在串中的序号；子
串的位置是它的首字符的位置。
? 4、串相等：两个串相等当且仅当它们完全一
致，即长度和对应位置上的字符都相同。
2010-5-14 计算机算法设计与分析 4
串的匹配
? 给定长度为 n的串 T = t1t2……t n (T称为正
文 )，以及另一个串 P = p1p2……p m (P称为
模式 )，查找模式 P在正文 T中首次出现或
所有出现的位置的过程称为模式匹配 。
2010-5-14 计算机算法设计与分析 5
简单的串模式匹配算法
? 将模式 P看成关键字，从正文 T的第 1个元
素开始，
? 逐个与 T中的 P[0]个元素比较；
? 如果这个长度为 P[0]的子串与模式 P相等，
则匹配成功；否则，又从 T的第 2个元素
开始进行同样的比较。
? 如此继续 T[0] – P[0] + 1步。
2010-5-14 计算机算法设计与分析 6
简单的模式匹配算法
? int StrMatch(SString S,SString P)｛
? i = 1； j = 1；
? while(i <= S[0] && j <= P[0])｛
? if (S[i] == P[j])｛ i++; j++;｝
? else {i = i – j + 2； j = 1}
? ｝
? if(j > P[0]) return i – P[0]；
? return 0;
? ｝
2010-5-14 计算机算法设计与分析 7
简单的模式匹配算法的评估
? 在回朔深度不大的情况下，模式匹配算
法的时间复杂度为 O(m+n)
? 在最坏情况下的时间复杂度为 O(n*m)。
2010-5-14 计算机算法设计与分析 8
KMP算法
? KMP算法是 D,Knuth与 V,Pratt和 J,Morris同时
发现的，故称为 Knuth_Morris_Pratt算法。
? 其思想是：每当匹配过程中出现字符不等时，
不是简单地从正文的下一个字符 (即 i+1)开始重
新比较，而是利用已经得到的“部分匹配”的
结果将模式串向右“滑动”尽可能远的一段距
离后，再进行比较。
? KMP算法的时间复杂度为 O(n+m)。
2010-5-14 计算机算法设计与分析 9
能向右滑动多远？
p1 … p k … p j … p m
s1 …… s i …… s n
当 si ? pj,就将模式向右移动。假设 pk和 si相比较：
s1 …… s i …… s n
p1 … p k … p j … p m
显然应有,si–k+1…s i–1 = p1…p k–1。
s …
…
而由前次的比较应有,si–k+1…s i–1 = j–k+1 …p j–1。
于是得到这样的结果：
p1…p k–1 = pj–k+1 …p j–1。
2010-5-14 计算机算法设计与分析 10
滑动的距离只取决于模式
? 模式滑动距离只取决于模式本身，与正文无关 。
? 设函数 next[j]为当模式中第 j个字符与正文中相
应字符“失配”时，在模式中需重新和正文中
该字符进行比较的字符的位置。
0 当 j=1时
? next[j] = max {k |1<k<j且 p1…p k–1= pj–k+1…p j–1}
1 当不存在相应的 k时
2010-5-14 计算机算法设计与分析 11
一个模式的 next(j)
? j, 1 2 3 4 5 6 7 8 9
? 模式, a b a a b a a a b
? next[j],
初始化,next[1] = 0。
0
没有相应的 k,next(j)为 1。
1 1
k = 2,下次从第二个元素开始比较。
2 2
依次以此类推可得其余元素的 next(j)。
3 4 5 2
2010-5-14 计算机算法设计与分析 12
滑动不会造成遗漏
? KMP算法不再是将正文依次和模式中的
元素逐个地进行匹配，而是当出现“失
配”时从模式的第 k(k=next(j))个元素开
始重新比较，这样会不会遗漏掉可以匹
配的子串呢？
? 不会的。因为滑动的距离 next(j)被定义为
满足 p1…p k–1= pj–k+1…p j–1的最大的 k。
2010-5-14 计算机算法设计与分析 13
滑动不会造成遗漏
? 引理 7.1,正文 S和模式 P比较时，若 si≠pj,则
S没有以 si–k0+1(next[j]<k0<i)开头的子串匹配 P。
? 证明：当 next[j]=0或 1时，结论显然成立。
? 当 next[j]>1时，假设结论不成立，即存在这样
的 k0,那么有 p1 p2 …p k0–1= si–k0+1si–k0+2 …s i–1。
? 从而有,p1 p2 …p k0–1= pj–k0+1pj–k0+2 …p j–1 (7.3)
? 由假设有 next[j]<k0<i。 这与 next[j]是满足 (7.3)
式的最大值相矛盾；所以结论成立。
2010-5-14 计算机算法设计与分析 14
KMP模式匹配算法
? int next[MaxStrLen]; //已算好的模式的 next值
? int KMP_StrMatch(SString S,SString P)｛
? int i = 1,j = 1,m = 0;
? while(i <= S[0] && j <= P[0])
? if (j = 0 || S[i] = P[j])｛ i++; j++;｝
? else j = next[j]; //失配时从 next[j]重新比较
? if(j > P[0]) m = i – j + 1;
? return(m);
? ｝
2010-5-14 计算机算法设计与分析 15
next(j)的计算
? 如何来计算模式 P的 next(j)?
? 首先，我们由定义可知 next(1) = 0；
? 其次，显然有 next(2) = 1；
? 现在我们来考虑 next(j+1)。
? 由 next(j)=k可知模式中有,p1…p k–1= pj–k+1…p j–1。
? 现在存在两种情况,pk = pj或者 pk ? pj。
? ⑴ 如果 pk = pj,于是 p1… p k–1pk= pj–k+1… p j–1pj。
从而有 next(j+1) = next(j) +1。
2010-5-14 计算机算法设计与分析 16
next(j)的计算
? ⑵ 如果 pk ? pj,显然 next(j+1) ? next(j)。
? 这实际是在将 p1… p k–1pk与 pj–k’+1… p j–1pj相匹配
时，出现了 pj与 pk失佩 。
p1 … p k–1 pk pj–k+1 … p j–k+1 pj ……
p1 … p k–1 pk pk ? pj
? 下一步拿 p1… p k–1pk中哪个元素和 pj相比较呢？
滑动多远？? 向右滑动 next(k),即比较 pnext(k)和 pj。
? 若这时有 pnext(k) = pj,则 next(j+1) = next(k) + 1；
? 若这时有 pnext(k) ? pj,则再重复以上的做法，
直至 k = 1。
2010-5-14 计算机算法设计与分析 17
next(j)的计算
? int next[MaxStrLen];
? void get_next(SString P) {
? j = 1; next[1] = 0; k = 0；
? while(j <= P[0])
? if (k == 0‖ P[k] = P[j])
? {++k; ++j; next[j] = k;}//next(j+1)=k +1
? else k = next[k]; }
初始化
循环逐个计算元素 j的 next(j)若 pk = pj,则 next(j+1)=k +1。
注意此处的 k,j都加了 1。
若 pk ? pj,则 比较 pnext(k)和 pj
2010-5-14 计算机算法设计与分析 18
一个模式的 next(j)
? j, 1 2 3 4 5 6 7 8 9
? 模式, a b a a b a a a b
? next[j],
初始化,j = 1; next[1] = 0; k = 0；
10
第一趟,j ; k = 0；
∵ k = 0
∴ {++k; ++j; next[j] = k;}
即,k = 1; j = 2; next(2) =1。
第二趟,j = 2; k =
∵ P[1] ? P[2]
∴ k = next[k] = 0
∵ k = 0
∴ {++k; ++j; next[j] = k;}
即,k = 1; j = 3; next(3) =1。
1
第三趟,3 。
∵ ] = P[3]
∴ ; j; t[j] ;}
即,2; j 4; t(4) 2。
2
第四趟,4 k = 2。
∵ 2 4
∴ t[2 1
∵ // k = 1
∴
即,5 5 。
2
第五趟,5 。
∵ P[2 5
∴
即,3 6 6 3。
3
第六趟,6 3。
∵ 3 6
∴
4 7 7 4。
4
第七趟,7 4。
∵ 4 7
∴
5 8 8 5。
5
第八趟,8 5。
∵ 5 ? 8
∴ k next[k] = next[5] = 2。
∵
∴ 2 1。
∵ 1 //
∴
即,9 9 2
2
至此循环结
束，求出了
所有元素的
next(j)。
2010-5-14 计算机算法设计与分析 19
Boyer-Moore算法
? Boyer-Moore串匹配算法 (简称 BM算法 )。
? 其思想是在匹配过程中，一旦发现在正
文中出现模式中没有的字符时就可以将
模式、正文大幅度地“滑过”一段距离。
? 同时考虑到多数不匹配的情形是发生在
最后的若干个字符，采用从左到右的方
式扫描将浪费很多时间，因此改自右到
左的方式扫描模式和正文，
2010-5-14 计算机算法设计与分析 20
Boyer-Moore算法
s1 …… s i …… s n
p1 … p j … p m
? 令 si = c。 如果在 pj和 pm之间没有符号 c的话，即
pj = c且是 j最大的, 就可以将模式右移 m – j个
元素，再与模式 P来进行比较。
p1 p j … p m 移到 si+m–j再来比较
? 如果符号 c是模式中没有的符号，就可以将模
式右移 m 个元素后，再与模式 P来进行比较。
2010-5-14 计算机算法设计与分析 21
滑动距离函数 dist(c)
? 为此,对给定的模式 P=p1p2…… pm,定义
从正文字母集 C到正整数的函数：
dist:C?{1,2,……,m}
为：
m c?P,或 c= pm且 c? pj(0<j<m)
? dist(c) =
m – j 否则 (j=max{c= pj,0<j<m)
2010-5-14 计算机算法设计与分析 22
BM串匹配算法
? int BM_string_Matching(char *s,char *p){
? int i,j,m,n;
? m=p[0]; n=s[0]; i=m;
? while(i<=n){
? j = m; k = i;
? while(j>0 && p[j] == s[k]){
? j--; k--;}
? if(j==0) return(i-m+1);
? else i+=dist[s[k]]; }
初始化从左至右循环匹配模式 P
从右至左循环比较每个符号
若 j = 0,则匹配成功，否则
将模式右移 dist[s[k]]。
2010-5-14 计算机算法设计与分析 23
函数 dist(c)的计算
? Void Computer_Distance(char *P){
? int i,j,m;
? m = P[0];
? for(i = 0; i < 256; i++)
? dist[i] = m;
? for(j = m –1; j > 1; j ––)
? if(dist[P[j]] = = m)
? dist[P[j]] = m – j;
? }
先令每一个符号的 dist(i) = m
对模式 P中符号的 dist进行修改
2010-5-14 计算机算法设计与分析 24
BM算法评估
? Computer_Distance函数的时间复杂度为
Θ(m)，
? 在最坏的情形下 BM算法的每次内循环次
数为 m,所以 BM算法最坏时间复杂度为
Θ(mn)。
2010-5-14 计算机算法设计与分析 25
KARP-RABIN串匹配随机算法
? 1987年 KARP和 RABIN教授发表了一种简单快
速的串匹配随机算法（简称 KR算法）。
? 基本思想是：先将模式和正文的每个长度为 m
的子串映都射成对应的整数值 (指印 )。完成这
个映射的函数称为指印函数。
? 然后对与模式具有相同指印的子串进行比较。
? 算法的主要时间是指印的计算和整数的搜索，
所以能够 达到快速匹配的目的。
2010-5-14 计算机算法设计与分析 26
,指印, 函数的定义
? 设模式 P为 p1p2…p m,正文 T为 t1t2…… tn,正文
和模式中出现的字符集合为 ?,且 | ? | = d。
? 对 ?上的 长度 m的符号串 ? = t1t2…t m,令整数
x = asc(t1)dm–1+ asc(t2)dm–1+…+ asc(t m)，
? 则符号串 ?的指印函数 K(?)为
K(?) = x mod q
? 这里 asc(c)为字符 c的 ASCII值,q是 [1,n2m]中随
机选取的适当大的素数。
2010-5-14 计算机算法设计与分析 27
KARP-RABIN算法的基本思路
? 首先计算模式，以及正文中所有长度为 m
的子串的指印函数。
? 然后匹配与模式串指印函数值相等的正
文中的子串，找到匹配串。
2010-5-14 计算机算法设计与分析 28
指印函数的递归计算
? 令 titi+1……t i+m–1的对应的整数为，
? yi = asc(ti)dm–1+ asc(ti+1)dm–2+…+ asc(t i+m–1)，
? 则 ti+1ti+2……t i+m的对应的整数为
? yi+1 = asc(ti+1)dm–1 +… +asc(ti+m–1)d+asc(ti+m)(yi – asc(ti)dm–1)d + asc(ti+m
? 因此，
?K(yi+1) = (yi – asc(ti)dm–1)d+asc(ti+m) mod qK(yi) – asc(ti)z) + asc(ti+m) mod q
? 其中,z = dm–1 mod q。
2010-5-14 计算机算法设计与分析 29
KARP-RABIN串模式匹配算法
? int K-RMatch(char *t,int n,char *p,int m){
? 数据说明；
? 计算指印函数计算中的 z;
? 计算模式 p和正文第一个子串的指印；
? 依据指印逐个匹配正文的子串； }
int i,j,k,z = 1,x = 0,y = 0;
for(i = 1; i < m; i++) z=(z*d) mod q;
这里 d是正文和模式中符号的个数,q是事先
随机选取的适当的素数。它们都是全局变量。
for(i = 1; i <= m; i++){
x = (x * d + asc(p[i])) mod q;
? y = (y * d + asc(t[i])) mod q;}
? 依据指印逐个匹配正文的子串； }
2010-5-14 计算机算法设计与分析 30
依据指印逐个匹配正文子串
? i = 1;
? while(i <= n – m){
? if(x == y){ k = 1; j = i;
? while(t[j] = p[k] && k <= m){j++; k++; }
? if(k > m) return(i)
? if(i <= n – m){
? y = ((y – z * t[i])*d + t[i + m]) mod q;
? i++;}
? return(0);}}}
从第一个子串开始循环逐个进行匹配。 若子串与模式的指印相同，
对其符号逐个进行比较。
匹配成功返
回其位置。
匹配不成功，计算下个
子串的指印，继续循环。
2010-5-14 计算机算法设计与分析 31
KARP_RABIN算法 的评估
? 不考虑子串匹配，时间复杂度为 O(n+m)。
? 考虑子串匹配，最差时间复杂度为 O(nm)。
? 只要选择的素数相当大，指印冲突几乎
没有，因而实际运行时间为 O(n+m)。
? 此算法很容易推广到二维情形，便于进
行算法的并行化，被广泛使用于计算机
图形处理领域。
2010-5-14 计算机算法设计与分析 32
小结
? 本章介绍了几种常用的符号串匹配算法：
Knuth_Morris_Pratt算法,Boyer-Moore算
法,Karp-Rabin随机算法。
? 这些算法的时间复杂度都是 O(n+m),最
差情况为 O(n*m)。
2010-5-14 计算机算法设计与分析 33
2010-5-14 计算机算法设计与分析 34
