KMP算法详解.doc

文档介绍：(1)以一个例子引入KMP算法
先看朴素模式匹配过程:
(a)S: a  b  b  a  b  a
       =  =  ≠
   P: a  b  a
(b)P3≠S3,P右移一位
   S: a  b  b  a  b  a
     
(c) P1≠S2,P右移一位
    S: a  b  b  a  b  a
              ≠
    P:       a  b  a
(d) P1≠S3,P右移一位
   S: a  b  b  a  b  a
                =  =  =
   P:          a  b  a
(e)匹配成功index(S,P)=4,  substr(S,4,3)=P
 
 
从匹配过程看:
    首先在(a)中p1=s1,p2=s2,p3≠s3,只需将模式右移到s3,不需将主串回溯到s2;
    其次,由于p1≠p2,可推出p1≠s2,做(b)的比较一定不等; 再由p1=p3,可以推出p1≠s3,做(c)的比较也一定不等。
    因此,由(a)便可直接将P右移三位跳到(d),从p1和t4开始进行比较,这样的匹配过程对S(主串)而言就消除了回溯。
    为要找到一个无回溯的匹配算法,关键在于当匹配过程中,一旦pj和si比较不等,存在:
 
substr(p,1,j-1)=substr(s,i-j+1,j-1)
pj≠si
 
改进的模式匹配算法的思想:
   在匹配过程中,当主串第i个字符与模式串第j个字符“失配”时,要产生模式串右移的位数和继续与主串(主串无回溯的)比较的字符,即应该用P中哪个字符和Si进行比较?把这个字符记为Pk,显然有k<j,并且对不同的j,k值也不相同。这个k 值仅依赖于模式P本身前j个字符的构成,而与目标S无关。
    一般用next[j]表示与j对应的k值,表明当模式中第j个字符与主串中第i个字符“失配”时,在模式中需重新和主串中第i字符进行比较的字符的位置。
 
s1 s2……………..si-k+1……..si-1 si   si+1……sn
    p1p2……pk-1  -k+1 …………pj-1 pj  pj+1…..pm
   假设此时应与模式串中第k个字符继续比较,则模式中前k-1个字符的子串必须满足下列关系:
    “p1p2…pk-1”=“si-k+1si-k+2…si-1”
由部分匹配知: “pj-k+1pj-k+2…pj-1”=“si-k+1si-k+2…si-1”
推得: “p1p2…pk-1”= “pj-k+1pj-k+2…pj-1
 
                 0     当j=1时
 next[j]=  Max{k|1<k<j且“p1p2…pk-1”= “pj-k+1pj-k+2…pj-1”
            1      其它情况
 
 
例:            ¯i=3
第一趟匹配  a b a b c a b c a c b a b
            a b c a c
                j=3   next[3]=1
                   ¯i