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

字符串匹配算法中国矿业大学计算机学院孟靖宇我们经常要在一段文本中某个特定的位置找出某个特定的字符或模式。由此，便产生了字符串的匹配问题。假设文本是一个长度为n的数组T[1...n]，模式是一个长度为m=n的数组P[1....m]。简单字符串匹配目标是找出所有在文本T=abcabaabcaabac中的模式P=abaa所有出现。该模式仅在文本中出现了一次，在位移s=3处。位移s=3是有效位移。n=length(T)m=length(P)intflag=1;for(s=0;sn-m;s++){flag=1;for(i=0;im;i++){if(P[i]!=T[s+i]){flag=0;break;}}if(flag){couts;break;}}简单的字符串匹配算法用一个循环来找出所有有效位移，该循环对n-m+1个可能的每一个s值检查条件P[0....m-1]=T[s....s+m-1]简单字符串匹配算法，上图针对文本T=acaabc和模式P=aab。n-m+1个可能的位移s中的每一个值，比较相应的字符的循环。所以，在最坏情况下，此简单模式匹配算法的运行时间为O（(n-m+1)m）。对于目的字串T是banananobano,要匹配的字串P是nano的情况只要P字串第一个字符先和T字串的第一个字符比较，如果相同就比较下一个，如果不同就把P右移一下，之后再从P的每一个字符比较，这个算法的运行过程如下图。nano时间复杂度是O(m*n)KMP算法TPTP覆盖函数所表征的是P本身的性质，可以让为其表征的是P从左开始的所有连续子串的自我覆盖程度。比如如下的字串abaabcabaa-1ab-1aba0abab1ababa2ababac-1abaabac0由于计数是从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个字符，如果覆盖函数值为ka[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)+1overlay(j)=koverlay(j+1)=k+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)过程.overlay(j)=koverlay(k)=hoverlay(j+1)=h+1有了覆盖函数，那么实现kmp算法就是很简单的了，我们的原则还是从左向右匹配，但是当失配发生时，我们不用把index向回移动，index前面已经匹配过的部分在P自身就能体现出来当发生在j长度失配时，只要把P向右移动j-overlay(j)长度就可以了。T字串匹配序号abbaaabaaababacindex1ababacindex2ababacindex3ababacindex4ababacindex5ababacindex6ababacindex7ababacindex8ababacindex9ababacindex10ababacababac-1-1012-1时间复杂度是O(m+n)BM算法后移位数=坏字符的位置-搜索词中的上一次出现位置坏字符规则：好后缀好后缀规则后移位数=好后缀的位置-搜索词中的上一次出现位置ABDCCABABCCCABABCCCAB最好时间复杂度是O(n/m)最坏时间复杂度是O(n*m)SUNDAY算法谢谢