第七章符号串.ppt

1、2020/7/15，计算机算法设计与分析，1。第7章，字符串，2020/7/15，计算机算法设计与分析，2。字符串的概念是由零个或多个字符组成的有限序列集，通常简称为字符串。在高级语言中，它们通常用引号()或单引号()括起来，例如，字符串a1a2an，我们通常将其写成“a1a2an”或a1a2an。2020/7/15，计算机算法设计与分析，3，字符串的几个概念，1，长度：字符串s中的字符数，记录为长度。长度为0的字符串称为空字符串。2.子串：字符串中的连续字符序列。包含子字符串的字符串称为主字符串。定义空字符串是任意字符串的子字符串。3.位置：字符的位置是它在字符串中的序列号；子字符串的位置是

2、其第一个字符的位置。4.字符串相等：当且仅当两个字符串完全一致时，即长度和相应位置的字符相同时，两个字符串相等。2020/7/15，计算机算法设计与分析，4，字符串匹配，给定长度为n的字符串T=t1t2tn (T称为文本)，而另一个字符串P=p1p2pm (P称为模式)，在文本T中查找模式P的第一次出现或所有出现的过程称为模式匹配。2020年7月15日，计算机算法设计与分析，5，简单字符串模式匹配算法，以模式p为关键字，从文本t的第一个元素开始，将其与t中的P0元素逐一比较；如果长度为P0的子串等于模式P，则匹配成功。否则，从T的第二个元素进行同样的比较.继续步骤T0 P0 1。2020年7月

3、15日，计算机算法设计与分析，6，简单模式匹配算法，串间匹配(s串s，s串p)I=1；j=1；而(i P0)返回I P0；返回0；2020/7/15，计算机算法设计与分析，7，简单模式匹配算法的评估，模式匹配算法的时间复杂度在小回溯深度的情况下为O(m * n)，在最坏的情况下为O(n*m)。2020/7/15，计算机算法设计与分析，8。KMP算法是由克努特、普拉特和莫里斯同时发现的，被称为克努特-莫里斯-普拉特算法。其思想是，每当在匹配过程中字符不相等时，不是简单地从文本的下一个字符(即1)重新比较，而是通过使用“部分匹配”的结果将模式串“滑动”到尽可能右边，然后进行比较。KMP算法的时间复

4、杂度为0(n m)。2020/7/15，计算机算法设计与分析，9，它能向右滑动多远？当si pj时，向右移动模式。假设pk与si相比较，显然应该是sik 1si1=p1pk1。和前面的比较应该是：sik 1si1=pjk 1 pj1。结果是p1pk1=pjk 1 pj1。2020/7/15，计算机算法设计与分析，10，滑动距离仅取决于模式，模式的滑动距离仅取决于模式本身，与文本无关。当模式中的jth字符与文本中的相应字符“不匹配”时，让函数nextj再次成为需要与文本中的字符进行比较的字符的位置。2020/7/15，计算机算法设计与分析，11，a模式的下一个(j ), j:1 23 4 5 6

5、 7 8 9模式：a b a b a a a b下一个j:0，没有相应的k，下一个(j)是1。1，1，k=2，下一次，从第二个元素比较。2、2等等来获得其他元素的下一个(j)。3，4，5，2，2020/7/15，计算机算法设计与分析，12，滑动不会造成遗漏，KMP算法不再是将文本与模式中的元素一一匹配，而是重新比较从k(k=下一个(j)元素的模式，当存在“不匹配”时，它将不会。滑动距离next(j)被定义为满足p1pk1=pjk 1pj1的最大k。2020/7/15，计算机算法设计和分析，13，滑动不会导致遗漏，引理7.1:当比较文本s和模式p时，如果sipj，则s不取sik0 1(nextj1)，假设存在这样的