文档介绍：第七章 字符串
2017/11/10
1
计算机算法设计与分析
字符串的概念
字符串是由零个或多个字符组成的有限序列集合,通常我们把字符串简称为串。
在高级语言中一般都是用引号(“)或单引号(’)括起来,例如,串a1a2…an,,我们一般记为“a1a2…an,”或‘a1a2…an,’。
2017/11/10
2
计算机算法设计与分析
串的几个概念
1、长度:串s中字符的个数,记为length(s) 。长度为0的串称为空串。
2、子串:串中的连续字符序列。而包含子串的串称为主串。定义空串是任意串的子串。
3、位置:字符的位置是它在串中的序号;子串的位置是它的首字符的位置。
4、串相等:两个串相等当且仅当它们完全一致,即长度和对应位置上的字符都相同。
2017/11/10
3
计算机算法设计与分析
串的匹配
给定长度为n的串T = t1t2……tn (T称为正文),以及另一个串P = p1p2……pm (P称为模式),查找模式P在正文T中首次出现或所有出现的位置的过程称为模式匹配。
2017/11/10
4
计算机算法设计与分析
简单的串模式匹配算法
将模式P看成关键字,从正文T的第1个元素开始,
逐个与 T中的P[0]个元素比较;
如果这个长度为P[0]的子串与模式P相等,则匹配成功;否则,又从T的第2个元素开始进行同样的比较。
如此继续T[0] – P[0] + 1步。
2017/11/10
5
计算机算法设计与分析
简单的模式匹配算法
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;
}
2017/11/10
6
计算机算法设计与分析
简单的模式匹配算法的评估
在回朔深度不大的情况下,模式匹配算法的时间复杂度为O(m+n)
在最坏情况下的时间复杂度为O(n*m)。
2017/11/10
7
计算机算法设计与分析
KMP算法
KMP算法是D. Knuth与V. Pratt和J. Morris同时发现的,故称为Knuth_Morris_Pratt算法。
其思想是:每当匹配过程中出现字符不等时,不是简单地从正文的下一个字符(即i+1)开始重新比较,而是利用已经得到的“部分匹配”的结果将模式串向右“滑动”尽可能远的一段距离后,再进行比较。
KMP算法的时间复杂度为O(n+m)。
2017/11/10
8
计算机算法设计与分析
能向右滑动多远?
p1 … pk … pj … pm
s1 …… si …… sn
当si pj,就将模式向右移动。假设pk和si相比较:
s1 …… si …… sn
p1 … pk … pj … pm
显然应有:si–k+1…si–1 = p1…pk–1。
s …
p1 …
而由前次的比较应有:si–k+1…si–1 = pj–k+1 …pj–1。
于是得到这样的结果:
p1…pk–1 = pj–k+1 …pj–1。
2017/11/10
9
计算机算法设计与分析
滑动的距离只取决于模式
模式滑动距离只取决于模式本身,与正文无关。
设函数next[j]为当模式中第j个字符与正文中相应字符“失配”时,在模式中需重新和正文中该字符进行比较的字符的位置。
0 当j=1时
next[j] = max {k |1<k<j且p1…pk–1= pj–k+1…pj–1}
1 当不存在相应的k时
2017/11/10
10
计算机算法设计与分析