标题: KMP算法引入及next推导 [打印本页]
作者: 51hei社区    时间: 2016-1-16 06:57
标题: KMP算法引入及next推导
本帖最后由 51hei社区 于 2016-1-16 06:58 编辑

                        前提条件:
S代表主串,
P代表模式串
下标从0开始

引入:下面两个字符串,判断P是否是S的子串
S: a b a b a b c a b c a c b ab
P: a b c
最普通的算法就是拿S和P一个一个比较,如果发现某一次匹配失败,则S从第一个P从头,再次进行比较.直到全部匹配结束.
缺点:复杂度最坏O(n*m),同时下标回溯发生在S和P中.

KMP算法:如果概念很熟悉.请直接跳过~~~
如果某一次匹配失败,那么回溯多少合适呢?
比如:
S : ababcabc
P: ababcaba
现在最后一个字符匹配失败.
我们来分析下最简单的模式匹配过程:S回溯到下标1.P从头开始,如下
ababcabc
ababcaba
继续匹配,第一次即失败. S回溯到下标2.P从头开始,如下
ababcabc
ababcaba
继续匹配,第三次即失败. S回溯到下标3.P从头开始,如下
ababcabc
ababcaba
继续匹配,第一次即失败. S回溯到下标4.P从头开始,如下
ababcabc
ababcaba
继续匹配,第一次即失败. S回溯到下标5.P从头开始,如下
ababcabc
ababcaba
继续匹配…结果到了c碰到第二次匹配失败…
注意第一次c是匹配到P的最后一个字符失败,第二次是匹配到P的第三个字符失败.
再这两次的过程中.做了很多工作..
我们发现是不是可以再这方面优化呢
我们发现无论S怎么进行回溯,其下标最后判断总是可以再c这个上面.
还有P回溯时,其实只要直接做
ababcabc
ababcaba
这一次就好了.
接着上面的问题,也就是说回溯多少合适呢?再这里P回溯2比较合适

证明:S0,S1,………………………………Si-1,Si
P0,P1,………………………………Pj-1,Pj
假设在Si和Pj中发生的匹配失败.那我们肯定知道
S0,S1,………………………………Si-1
P0,P1,………………………………Pj-1
是相等的.
假设我们P回溯到下标k比较合适,也就是说下一次比较是Si和Pk.
那么肯定有
S0,S1,………………………………Si-1,Si
P0,P1,………………………………Pj-1,Pj
P0,P1,…………Pk-1,Pk
P0,P1,…………Pk-1 =Si-k…………Si-1因为S0,…Si-1 和P0,…Pj-1是相等的,且j是大于k的值
所以P0,P1,…………Pk-1 =Pj-k, …………Pj-1
所以看出.S不用回溯.回溯只跟P有关.
我们既然每次都可以回溯一个比较合理的值,那算法就非常好写了.
关键就是这个k如何去寻找...这个下回再说.


--------------------------------------------------


上回说到.要确保P0,P1,…………Pk-1 = Pj-k, …………Pj-1这个表达式成立
则需要找到里面的k值,next有以下定义:

既然是推导,肯定要设定一些条件.我们假设
已有next[j] = k ,求next[j+1] = ?
既然已有next[j] = k,那么肯定有.P0,P1,…………Pk-1  =  Pj-k,…………Pj-1,但我们对于Pk 和 Pj的关系不清楚,让我们分开讨论
如果此时Pk = Pj
那么肯定有 P0,P1,…………Pk-1  =  Pj-k, …………Pj-1,Pj明显看到左右的长度都加了1.也就是说在原来的基础上长度加了1.
则 next[j+1] = next[j] + 1 = k + 1;
如果此时Pk ≠ Pj
这地方很绕...最起码我学习的时候是...请详细看,我也尽量分析的详细点.
说明不会含有[0,k]长度的字符串与[k+1,j-1]
虽然这个不相等,但有可能比k小的前缀是相等的.但到底Pj 和前面的哪个字符串相等呢?
这是不是又牵扯到一个模式匹配的问题捏?  答案是的.
把模式串的后面部分看作新的主串 Pj-k, …………Pj-1,Pj
模式串前面部分看作新的模式串  P0,P1,…………Pk-1,Pk 去寻找新的匹配k'
这时候的步骤是:
1:出现了Pj和Pk不同.这时候根据KMP算法,需要回溯P产生k'.其实就是移动next(k).
2:由于带入后末尾2个匹配就是一样的了.Pk' = Pj所以就可以得出,从j+1的字符之前存在一个长度为k'的最长字串
   P0……..Pk' = Pj-k’……Pj.也就是说next[j+1] = k’+1
   next[j+1] = next(k) + 1;

举个例子吧.
0         1        2        3        4        5        6        7        8        9          10
-1
0
0
1
2
0
1
2
3
4
?
a
b
a
b
c
a
b
a
b
a
b
现在求next(10)?
分解成next(9+1) ,已知next(9) = 4 ,判断P4 == P9?
因为P4=c P9=a 所以不相等next(9+1) = next(4) + 1 = 3  请自己验证.
下面用白话解释上面的公式下,看next(9) = 4,那从9往前看4个 是abab....肯定第一个到第四个也是abab
假设如果next(10) = 5 如果从10往前面看ababa 第一个到第五个肯定也是ababa这个是肯定的.但实际上第一个到第五个是ababc
但p[19] = a ...发现了吧是拿a和c比的.结果发现不同..
说明[0,k]长度的字符串与[k+1,j-1]是不会相同的.只有从[0,k]中找一个k'来进行小范围的匹配的...这个东西明显就是next[k]...
希望我说明白了.哈哈

再来一个吧next(6)?
分解成next(5+1) ,已知next(5) = 0 ,判断P5 == P0?
因为P5=a P0=a 所以相等next(5+1) = next(5) + 1 = 1  请自己验证.


其实next算法还有能可以优化的...因为有一种极端的情况.下回说~

-------------------------------------------


                        还有一种特殊情况需要考虑:
例如:
aaabaaabaaabaaabaaab
aaaab
使用上次我们说的算法计算出next
next[j] = -10123
下面进行匹配过程:
s[3] = b ,p[3] = a 不匹配,P回溯到next[3].发现还是a,再回溯还是a再回溯....
其实a和a是相同的,我们应该有个策略告诉他,不需要再重复比较了.
于是
本来sj 不等于 pi的   那么要sj和pk相比. 而k=next[ i]的
此时如果pi=pk的话,那么sj肯定也不等于pk,所以就不用比了.
这时候回溯多少可以与next[next[ i]]相同....
修正后
next[j] = –1 -1 -1 -1 3
KMP算法告一段落~有时间把算法贴上来~

附代码:VC2005编译成功
#include<string.h>

template<typenameT>
classPatternMatch
{
public:
   virtual~PatternMatch(){}
   
   virtualintmatch(constT* source,intsourcelen,constT* pattern,intpatternlen) = 0;
};

template<typenameT>
classKmp:publicPatternMatch<T>
{
public:
   virtualintmatch(constT* source,intsourcelen,constT* pattern,intpatternlen)
   {
        intres = -1;
        if (!source || sourcelen<=0|| !pattern ||patternlen<=0)
        {
           returnres;
        }
        int* next = newint[patternlen];
        if (!next)
        {
           returnres;
        }

        do
        {
           if (generate_next(pattern,patternlen,next)<0)
           {
               break;
           }
           inti = 0;
           intj = 0;
           while(i<sourcelen&&j<patternlen)
           {
               if(-1==j ||source[i]==pattern[j])
               {
                   ++i;
                   ++j;
               }
               else
               {
                   j = next[j];
               }
           }
           if (j>=patternlen)
           {
               res =i-patternlen;
           }
        }while (false);

        delete []next;
        returnres;
   }
protected:
   intgenerate_next(constT* pattern,intpatternlen,int* nextarray)
   {
        if (!pattern || patternlen<=0|| !nextarray)
        {
           return -1;
        }

        nextarray[0] = -1;

        inti = 0;
        intj = -1;
        while (i<patternlen-1)
        {
           if(-1==j ||pattern[i]==pattern[j])
           {
               ++i;
               ++j;
               if (pattern[i]!=pattern[j])
               {
                   nextarray[i] = j;
               }
               else
               {
                   nextarray[i] = nextarray[j];
               }
           }
           else
           {
               j = nextarray[j];
           }
        }
        return 1;
   }
};

voidmain()
{
   Kmp<char>a;
   intpos = a.match("abcde",5,"cd",2);
}










欢迎光临 (http://www.51hei.com/bbs/) Powered by Discuz! X3.1