图解Kmp算法

前言：最近在复习数据结构，又偶遇kmp，居然没感觉了，理不出思路，特别是对next[]函数的求解更没感觉，于是静下心花了2天时间，细细重新理解了一遍，这篇文章仅当自己在学习kmp过程中的一点感悟，或许不一定理解的完全透彻，只是在记录我学习过程中思维的灵感，以便今后回来感受。好了废话不多说了，直接进入正题。

 

1.什么是kmp？

   它是一种字符串匹配算法。与以往字符串匹配算法的区很简单就是，kmp算法中主串的i值不回溯，子串的j值每次回溯不一定从0开始，它每次回溯值j = next[j].看下面的图就能一清二楚了。

 
     

 

    有了这个两个图：就很容易理解kmp算法了。只要把字符串匹配想象成一个有齿痕的长尺子和一个有齿痕的短尺子，长尺子不动，短尺子在长尺子身上找相同的齿痕，那么要想很快匹配成功的话，那么我们肯定是先找长齿痕与短齿痕最相似的地方先去比较一下，如果发现不匹配，在找相似程度小一点的去比较，然后依次减少相似度慢慢一次次比较下去，直到成功找到。这里我只是为说明kmp算法的核心思维，其具体细节我就没有一一纠结，你们自己可以在纸上用例子去观察观察。具体实现算法我也不想多讲，因为网上很多。 

 

二：关于next[]函数的推导。

 

   可以说kmp算法难就难在next[]的推导，至少我学习的过程中是这么感觉到的。到不是说要自己求出next[]值难，而是难在理解它是怎么找到字符串的相似度的。特别是网上求next[]函数代码的理解，稍后详细解释。

 

首先还是说明一下next[]函数的含义。

  1.首先对kmp算法来讲：next[] 函数是针对子串来讲的。它是求子串中，每一个位置的之前的字符串的相似度。例如：next[j] = k 的含义：就是子串的j个位置之前的字符串的相似度。（求next[]过程中理解）

  子串第j个位置的字符与主串字符不匹配时，下一个匹配的位置为子串第k个位置。（与主串匹配过程中的理解）

 两种理解都可以，前一种理解在求next[]的过程中比较容易。第二种理解比较适合在与主串匹配的过程中。

     网上很多人都是这样理解的：当主串第j位置上的字符与子串不相等时，下一个要匹配的字符就是子串第k个位置的字符。这样讲把j值重点落在主串身上了，要知道子串长度肯定少于子串的，所以如果j值大于子串的长度，那next[]数组不超出范围了吗？所以对于网上这种讲法保留意见。

 

这里说的相似度理解：不是说有相同的就是，而是说的中心对称。例如：abcabc 他们就是。而对于字符串

abcabb 不能说明它们相似。因为他们不是中心对称。可以理解字符串的前辍等于字符串的后辍。下面用一个例子说明问题:

假定一个字符串:

位置： 01234567

子串p：abcabckfg

p[0]位置: 由于a字符前无元素，所以谈不上相似度。所以可以取值为next[0] = -1;(网上也有表示为0的，那是因为它的位置是1234567)；

 

 p[1]位置：由于b位置前面的字符串为只有一个a，所以他相似度为next[1]=0;

 

p[2],p[3] 位置之前的字符串分别为：ab,abc 也无相似的。 next[2],next[3] = 0 ;

p[4].位置：字符串为abca   可以看到红色部分相同，即前辍=后辍。next[4] = 1 ;理解：当p[4]位置与主串不匹配时，下一个要匹配的位置即为j = 1.即为b字符。

后面的就不一一推导，原理类似。

 

 

三：关于next[] 数组推导代码理解。

   递归思想:因为已经知道next[0] = -1;next[1] = 0 了。能否推导的出，现在的问题就是能否由

next[j]=k 推出next[k+1]。在推导之前，首先要明确一个问题就是：pj,pk 究竟是表示什么？

 因为网上有文章讲分情况：pj = pk 或者pj!=pk 两种去推导。而且把求解next[]的过程看成是与子串相同的字符串匹配过程，这很让人迷惑的，因为不是求子串的相似度么，为什么要拿相同的来比较？而且理解pj = pk 的过程也不清楚。认为pj 就是子串的的j个位置的字符，pk就是主串的第k个位置的字符。其实这种理解是不恰当的。

先看看代码吧：(网上找的)用代码对照例子说明

void getNext(char *p,int *next)
{
    int j,k;
    next[0]=-1;
    j=0;
    k=-1;
    while(j<strlen(p)-1)
    {
        if(k==-1||p[j]==p[k])    //匹配的情况下,p[j]==p[k]
        {
            j++;
            k++;
            next[j]=k;
        }
        else                   //p[j]!=p[k]
            k=next[k];
    }
}

 

假设要求字符串ababdf的next[]数组

字符串：ababdf

位置：    012345

 

因为next[0],next[1] 的值我们都知道了。所以一开始我们求的是next[2] 即第3个位置之前字符串的相似度。要求next[2],即看ab他们的相似度高不高，所以就要比较p[0]是否等于平p[1]。

如图理解：

 当i 等于2时如图：

 后面依次i++，直到i到最后一个字符，这里就不在细说。由代码结合图我们可以知道：每一次比较pi,pj其实是在比较字符串的前辍和后辍。每次判断j位置之前的字符串，看前辍是否等于后辍。 

 

上面的求解代码是经过优化而来，有一定的难度，不理解的同学可以依次跟着程序走将过程画出来，就清楚了，其实就是每次i往前移动时，就是在匹配i之前的那个字符是否和字符串的前辍某个字符相等，如果不相等，j = next[j],j回溯，直到找到，如果当j = 0还是没找到，那么说明该位置没有相等的了。此时next[i] = 0.

其实上面写的求next[]函数代码写的比较精巧，如果求串ababaf的next[]其核心思想就是：如图：

 

如果还是不理解，其实还可以直接求解,不就是比较子串的前辍和后辍相等嘛：

代码如下：

void getNext(char *p,int *next)
{
    int i,j,temp;
    for(i=0;i<strlen(p);i++)
    {
        if(i==0)
        {
            next[i]=-1;     //next[0]=-1
        }
        else if(i==1) 
        {
            next[i]=0;      //next[1]=0
        }
        else
        {
            temp=i-1;
            for(j=temp;j>0;j--)
            {
                if(equals(p,i,j))
                {
                    next[i]=j;   //找到最大的k值
                    break;
                }
            }
            if(j==0)
                next[i]=0;
        }
    }
}
 
bool equals(char *p,int i,int j)     //判断p[0...j-1]与p[i-j...i-1]是否相等  
{
    int k=0;
    int s=i-j;
    for(;k<=j-1&&s<=i-1;k++,s++)
    {
        if(p[k]!=p[s])
            return false;
    }
    return true;
}

 

 其实关于next[] 数组还可以优化，在这里就暂且不讲了。