【算法设计与分析】符号串.pptVIP

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