算法导论之字符串匹配算法.pptx

字符串匹配算法;我们经常要在一段文本中某个特定的位置找出 某个特定的字符或模式。由此，便产生了字符串的匹配问题。;简单字符串匹配;目标是找出所有在文本T=abcabaabcaabac中的模式P=abaa所有出现。 该模式仅在文本中出现了一次，在位移s=3处。位移s=3是有效位移。;n = length(T)m = length(P) int flag=1;for(s = 0 ; s n-m ; s++) { flag=1; for(i = 0 ; i m ; i++) { if (P[i] != T[s+i]) {flag=0;break;} } if(flag) {cout s; break;} }???????;简单的字符串匹配算法用一个循环来找出所有有效位移，该循环对n-m+1个可能的每一个s值检查条件;简单字符串匹配算法，上图针对文本T=acaabc 和模式P=aab。 n-m+1个可能的位移s中的每一个值，比较相应的字符的循环。 所以，在最坏情况下，此简单模式匹配算法的运行时间为O（(n-m+1)m）。;对于目的字串T是banananobano,要匹配的字串P是nano的情况 只要P字串第一个字符先和T字串的第一个字符比较，如果相同就比较下一个，如果不同就把P右移一下，之后再从P的每一个字符比较，这个算法的运行过程如下图。;nano;KMP算法;;;覆盖函数所表征的是P本身的性质，可以让为其表征的是P从左开始的所有连续子串的自我覆盖程度。比如如下的字串;由于计数是从0始的，因此覆盖函数的值为0说明有1个匹配，其中-1表示没有覆盖，那么何为覆盖呢，下面比较数学的来看一下定义，比如对于序列 ? a[0]a[1]...a[j-1]a[j] ? 要找到一个k,使它满足 a[0]a[1]...a[k-1]a[k]= a[j-k]a[j-k]...a[j-1]a[j] 而没有更大的k满足这个条件，就是说要找到尽可能大k,使P前k字符与后k字符相匹配，k要尽可能的大，原因是如果有比较大的k存在，而我们选择较小的满足条件的k，;在红色部分失配，正确的结果是k=1的情况，把P右移4位，如果选择k=0,右移5位则会产生错误。计算这个overlay函数的方法可以采用递推，可以想象如果对于pattern的前j个字符，如果覆盖函数值为k a[0]a[1]...a[k-1]a[k]= a[j-k]a[j-k+1]...a[j-1]a[j];则对于pattern的前j+1序列字符，则有如下可能⑴???? P[k+1]==P[j+1] 此时 overlay(j+1)=k+1=overlay(j)+1;⑵???? P[k+1]≠P[j+1] 此时只能在P前k+1个子符组成的子串中找到相应的overlay函数，h=overlay(k),如果此时P[h+1]==P[j+1],则overlay(j+1)=h+1否则重复(2)过程.;;有了覆盖函数，那么实现kmp算法就是很简单的了，我们的原则还是从左向右匹配，但是当失配发生时，我们不用把index向回移动，index前面已经匹配过的部分在P自身就能体现出来当发生在j长度失配时，只要把P向右移动j-overlay(j)长度就可以了。;　;BM 算法;后移位数 = 坏字符的位置 - 有哪些信誉好的足球投注网站词中的上一次出现位置;好后缀;好后缀规则;最好时间复杂度是O(n/m);SUNDAY算法;谢 谢