串的模式匹配.

串的模式匹配算法雅礼朱全民串的基本操作串的连接（concat）求子串（substr---Pascal中的copy函数）插入函数（insert）删除函数（delete）定位函数（index---Pascal中的pos函数）模式匹配算法模式匹配基本思想：从主串s的第一个字符起和模式的第一个字符比较之，若相等，则继续逐个比较后序字符，否则从主串的第二个字符起再重新和模式的字符比较之。依次类推，直至模式t中的每个字符依次和主串s中的一个连续字符序列相等，则称匹配成功，否则匹配不成功。算法框架FUNCpos(p,s:string):integer;{求模式串t在主串s中的位置的定位函数}i:=1;j:=1{指针初始化}WHILE(i=length(s))and(j=length(p)DOIFs[i]=p[j]THEN[i:=i+1;j:=j+1]{继续比较后续字符}ELSE[i:=i-j+2;j:=1];{指针后退重新匹配}IFjlength(p)THENRETURN(i–length(p))ELSERETURN(0)ENDF;复杂性分析:最坏情况为O(n*m)例如:模式串为‘00000001’主串为:‘0000000000000000000000000000000000000000000000000000000000001’KMP(Knuth-Morris-Pratt)算法KMP的基本原理由(1)可知,pj-k+1pj-k+2…pj-1=si-k+1si-k+2…si-1--------(1)由(2)可知,p1p2…pk-1=si-k+1si-k+2…si-1--------(2)所以有p1p2…pk-1=pj-k+1pj-k+2…pj-1--------(3)怎样求KKMP示例KMP算法框架FUNCKMP(p,t:string):integer;i:=1;j:=1{指针初始化}WHILE(i=length(s))and(j=length(p)DOIFs[i]=p[j]THEN[i:=i+1;j:=j+1]{继续比较后续字符}ELSEj:=next[j];{模式串向右滑动next[j]}IFjlength(p)THENRETURN(i–length(p))ELSERETURN(0)ENDF;怎样求next[j]?首先有,next[1]=0,设next[j]=k,表明:p1p2…pk-1=pj-k+1pj-k+2…pj-1(1)若pk=pj,则在模式串中有,p1p2…pk=pj-k+1pj-k+2…pj所以,next[j+1]=k+1(2)若pkpj,则杂模式串中有p1p2…pkpj-k+1pj-k+2…pj则可将求next函数的问题看成整个模式串既是主串又是模式串的问题,应将模式串滑动到next[k]个字符和主串的第j个字符相比较.若next[k]=k’,且pj=pk’,则说明在主串中第j+1个字符之前存在一个长度为k’的最长子串,和模式串中从首字符起长度为k’的子串相等,即p1p2…pk’pj-k’+1pj-k+2…pj也就是说next[j+1]=k’+1=next[k]+1求NEXT算法Procget_next(t:string);{next为全程变量}j:=1;k:=0;next[1]:=0;Whilejlength(p)doif(k=0)or(p[j]=p[k])then[j:=j+1;k:=k+1;next[j]:=k]elsek:=next[k]ENDP该算法的时间复杂度仅为O(length(p))扩展KMP算法给定母串S，和子串T。定义n=|S|,m=|T|，extend[i]=S[i..n]与T的最长公共前缀长度。请在线性的时间复杂度内，求出所有的extend[1..n]。容易发现，如果有某个位置i满足extend[i]=m，那么T就肯定在S中出现过，并且进一步知道出现首位置是i——而这正是经典的KMP问题。因此可见“扩展的KMP问题”是对经典KMP问题的一个扩充和加难。一个例子这里为了计算extend[1]，我们进行了11次比较运算aaaaaaaaaabaaaaaaaaaaaaaa红色箭头表示失配在第11个位置失配aaaaaaaaaabaaaaaaaaaaaaaa红色箭头表示失配在第11个位置失配extend[2]=9。为了计算extend[2]，我们是不是也要进行10次比较运算呢？分析不然。因为通过计算extend[1]=10，我们可以得到这样的信息：S[1..10]=T[1..10]S[2..10]=T[2..10]。计算extend[2]的时候，实际上是S[2]开始匹配T。因为S[2..10]=T[2..10]，所以在匹配的开头阶段是“以T[2..10]为母串，T为子串”的匹配。不妨设辅助函数next[i]表示T[i..m]与T的最长公共前缀长度。对于这个例子，next[2]=10。也就是说：T[2..11]=T[1..10]T[2..10]=T[1..9]S[2..10]=T[1..9]。这就是说前9位的比较是完全可以避免的！我们直接从S[11]T[10]开始比较。这时候一比较就发现失配，因此extend[2]=9。算法设extend[1..k]已经算好，并且在以前的匹配过程中到达的最远位置是p。最远位置严格的说就是i+extend[i]-1的最大值，其中i=1,2,3,…,k；不妨设这个取最大值的i是a。(下图黄色表示已经求出来了extend的位置)1…kk+1pSS:第一种情况k+Lp上面的红色部分是相等的。蓝色部分肯定不相等，否则就违反了“next[i]表示T[i..m]与T的最长公共前缀长度”的定义。（因为next[k-a+2]=L，如果蓝色部分相等的话，那么就有next[k-a+2]=L+1或者更大，矛盾）。无需任何比较就可以知道extend[k+1]=L。同时a,p的值都保持不变，kk+1，继续上述过程。1…kk+1…p1…LL+1……mST第二种情况k+L=p上图的紫色部分是未知的。因为在计算extend[1..k]的时候，到达过的最远地方是p，所以p以后的位置从未被探访过，我们也就无从紫色部分是否相等。这种情况下，就要从S[p+1]T[p-k+1]开始匹配，直到失配为止。匹配完之后，比较extend[a]+a和extend[k+1]+(k+1)的大小，如果后者大，就更新a。整个算法描述结束。1…kk+1…pp+11……LST……复杂性分析很容易看出，在计算的过程中，凡是访问过的点，都不需要重新访问了。一旦比较，都是比较以前从不曾探访过的点开始。因此总的时间复杂度是O(n+m),是线性的。还剩下一个问题：next这个辅助数组怎么计算？复杂度是多少？计算next实际上以T为母串、T为子串的一个特殊“扩展的KMP”。用KMP算法计算next即可。认真领会上面算法的思想，即：已经访问过的点绝不再访问，充分利用已经得到的信息。DNA病毒科学家最近发现了某种病毒，通过对该病毒的分析，它的DNA是是环状的，科学家为了方便研究，将病毒DNA表示成由一些字母组成的字符串，现在科学家怀疑有人中了这种病毒，如何判断是否中了病毒呢？主要是看这种病毒代码是不是在人的DNA中出现过，如果出现过，则此人中了病毒，否则没有中病毒。例如，假设人的DNA代码为abcddcba，而病毒代码为ccdd，则abcddcba的下划线部分为病毒部分，该人中了毒。科学家有一些任务，他们已找出了病毒的DNA和人的DNA，现在要你提供帮助，看看哪些是否中了毒。第一行一个数n，表示有n个任务，（k=300）。接下来的每个任务都包括两行，第2i行的字符串表示第i个人的DNA(长度=8000)，第2i+1行的字符串，表示第i个病毒的DNA。（长度=8000）。（注意，人的DNA是线性的，而病毒DNA是环状的)输出：DNA.outn行，每行一个词”YES”或者“NO”。分别所对应那个任务的判断情况。样例：DNA.INDNA.OUT2YESbbabYESabbabababab分析扩展kmp：即可以在O(n+m)的时间内，求出模式s的每一个位置i可以和母串的每个位置j匹配到哪儿。然后求出a[i]:s的每一个位置向后匹配与t开始向后匹配可以匹配到哪儿。然后求出b[i]:从s的每一个位置向前匹配与t从后开始向前匹配可以匹配到哪儿。如果a[i]+b[i-1]=length(t)就输出’YES’,否则是’NO’。