【字符串匹配讲解 】

KMP算法是一种字符串模式匹配算法，不同的来源讲解方式也不一样，很容易混乱，在这里以一种特殊的方式来讲解KMP算法，希望大家不再被这个问题所困扰。

 一些基础问题

什么是字符串的模式匹配？
给定两个串S=“s1s2s3 …sn”和T=“t1t2t3 …tn”，在主串S中寻找子串T的过程叫做模式匹配，T称为模式。
如何寻找？
我们先从比较好理解的暴力匹配（朴素模式匹配BF算法）开始，进而引出KMP算法。
二. 暴力匹配（朴素模式匹配BF）

规定i是主串S的下标，j是模式T的下标。假设主串S匹配到 i 位置，模式串T匹配到 j 位置。

如果当前字符匹配成功（即S[i] = T[j]），则i++，j++，继续匹配下一个字符；
如果失配（即S[i] != T[j]），令i = i - (j - 1)，j = 0。相当于每次匹配失败时，i 回溯到本次失配起始字符的下一个字符，j 回溯到0。
 

int BF(char S[],char T[])
{
    int i=0,j=0;
    while(S[i]!='\0'&&T[j]!='\0')
    {
        if(S[i]==T[j])
        {
            i++;
            j++;
        }
        else
        {
            i=i-j+1;
            j=0;
        }
    }
    if(T[j]=='\0') return (i-j);     //主串中存在该模式返回下标号 
    else return -1;     //主串中不存在该模式 
}

现有主串S：ababcabcacba，

    模式串T：abcac。

我们来看一下是如何匹配的。i从0开始，j也从0开始。

在第一次匹配中，i从0开始，j从0开始。当i=2，j=2时匹配失败，此时i回溯到1，j回溯到0。

第二次匹配中，i从1开始，j从0开始。当i=1，j=0时匹配失败，此时i回溯到2，j回溯到0。

第三次匹配中，i从2开始，j从0开始。当i=6，j=4时匹配失败，此时i回溯到3，j回溯到0。

第四次匹配中，i从3开始，j从0开始。当i=3，j=0时匹配失败，此时i回溯到4，j回溯到0。

第五次匹配中，i从4开始，j从0开始。当i=4，j=0时匹配失败，此时i回溯到5，j回溯到0。

第六次匹配中，i从5开始，j从0开始。i=10，j=5，T中全部字符比较完，匹配成功，返回本次匹配起始位置下标i - j。（i=9和j=4的时候匹配成功，i和j会再加一次，所以i=10，j=5）

可见，如果i已经匹配了一段字符后出现了失配的情况，i会重新往回回溯，j又从0开始比较。这样浪费的大量的时间。在第三次匹配结束后，我们可以发现：i=3和j=0，i=4和j=0以及i=5和j=0是不必进行的，因为从第三次部分匹配过程中我们可以得出，主串中第3，4，5个字符必然是‘b’，‘c’，‘a’（即与模式串的第1，2，3个字符分别对应相等），而模式的首字符是‘a’，它分别与‘b’，‘c’不等，与‘a’相等。如果将模式向右滑动3个字符继续进行i=6和j=1时的字符比较，很明显会加快进程。这样就引出了我们的KMP算法，不回溯i，加快匹配效率。

三. KMP算法

1. 背景
KMP算法一种改进的模式匹配算法，是D.E.Knuth、V.R.Pratt、J.H.Morris于1977年联合发表，KMP算法又称克努特-莫里斯-普拉特操作。它的改进在于：每当从某个起始位置开始一趟比较后，在匹配过程中出现失配，不回溯i，而是利用已经得到的部分匹配结果，将一种假想的位置定位“指针”在模式上向右滑动尽可能远的一段距离到某个位置后，继续按规则进行下一次的比较。
2. 算法流程 （这部分读完可能会有很多问题，没关系，我们会针对每一步进行详细的讲解）
规定i是主串S的下标，j是模式T的下标。现在假设主串S匹配到 i 位置，模式串T匹配到 j 位置。

如果j = -1，则i++，j++，继续匹配下一个字符；
如果S[i] = T[j]，则i++，j++，继续匹配下一个字符；
如果j != -1，且S[i] != P[j]，则 i 不变，j = next[j]。此举意味着失配时，接下来模式串T要相对于主串S向右移动j - next [j] 位。

int KMP(int start,char S[],char T[])
{
    int i=start,j=0;
    while(S[i]!='\0'&&T[j]!='\0')
    {
        if(j==-1||S[i]==T[j])
        {
            i++;         //继续对下一个字符比较 
            j++;         //模式串向右滑动 
        }
        else j=next[j];
    }
    if(T[j]=='\0') return (i-j);    //匹配成功返回下标 
    else return -1;                 //匹配失败返回-1 
}

（1）next是什么？？？它是怎么来的？？？

首先我们来解释一个名词：最长公共前后缀。假设有一个串P=“p0p1p2 …pj-1pj”。如果存在p0p1…pk-1pk = pj-kpj-k+1…pj-1pj，我们就说在P串中有一个最大长度为k+1的公共前后缀。

（2）如何寻找前后缀？？？

找前缀时，要找除了最后一个字符的所有子串。
找后缀时，要找除了第一个字符的所有子串。
问题（2）已解决

现在有串P=abaabca，各个子串的最大公共前后缀长度如下表所示：

这样，公共前后缀最长长度就会和串P的每个字符产生一种对应关系：

这个表的含义是在当前字符作为最后一个字符时，当前子串所拥有的公共前后缀最长长度。例如当c作为最后一个字符时，当前子串abaabc并没有公共前后缀。
接下来我们就用这个表来引出next数组，next 数组的值是除当前字符外（注意不包括当前字符）的公共前后缀最长长度，相当于把上表做一个变形，将表中公共前后缀最长长度全部右移一位，第一个值赋为-1。例如c对应next值的意义是，c之前（不包括c）的子串abaab所拥有的公共前后缀最长长度为2，我们称next数组中的值为失效函数值，也就是c的失效函数值为2。（当然这是我们手动推得，我们后续会用编程思想来推得next数组）

我们手动推得了next数组，那就来体验一下KMP算法的流程：现在有主串S：ababcabcacbab，模式串T：abcac。i从0开始，j也从0开始。
根据上述方法可以知道，T的中每个字符对应的失效函数值为：

第一次匹配中，i从0开始，j从0开始。当i=2，j=2时匹配失败，此时i不动，next[j]=next[2]=0，接下来模式串T要相对于主串S向右移动j - next [j] = 2 位，j回溯到0。

第二次匹配中，i从2开始，j从0开始。当i=6，j=4时匹配失败，此时i不动，next[j]=next[4]=1，接下来模式串T要相对于主串S向右移动j - next [j] = 3位，j回溯到1。

第三次匹配中，i从6开始，j从1开始。当i=10，j=5时匹配成功，返回i - j = 5。

我们根据next数组进行匹配，不失一般性的话，我们做如下总结：
当主串S与模式串P失配时，j=next[j]，P向右移动j - next[j]。也就是当模式串P后缀pj-kpj-k+1…pj-1与主串S的si-ksi-k+1…si-1匹配成功，但是pj和si失配时，因为next[j]=k，相当于在不包含pj的模式串中有最大长度为k的相同前后缀，也就是p0p1…pk-1 = pj-kpj-k+1…pj-1，所以令j = next[j]，让模式串右移j - next[j]位，使模式串p0p1…pk-1 与主串si-ksi-k+1…si-1对齐，让pk和si继续匹配。如下图所示：

KMP的next数组告诉我们：当模式串中的某个字符跟主串中的某个字符失配时，模式串下一步应该跳到哪个位置。如模式串中在j 处的字符跟主串在i 处的字符匹配失配时，下一步用next [j] 处的字符继续跟主串i 处的字符匹配，相当于模式串向右移动 j - next[j] 位。

问题（1）已解决

好了，至此我们把next原理全部讲完，但是我们不能只停留在手动推导的层面上，我们再从编程下手继续理解next数组，最后再推出KMP算法。

3. 递推求next数组

我们很容易的可以知道，next[0] = -1。next[1] = 0也是容易推得的。那么（3）当j>1时，如果我们已知了next[j]，那么next[j+1]怎么求得呢？？？

假定我们给定了某模式串，且已知next[j] = k，现在求得next[j+1]等于多少。

我们分两种情况分析：

当pk=pj时，next[j + 1] = next[j] + 1 = k + 1，代表字符E前的模式串中，有长度k+1 的最大公共前后缀。

当pk ! = pj时，说明p0p1…pk-1pk != pj-kpj-k+1…pj-1pj，这时ABC与ABD不相同，也就是字符E前的模式串中没有长度为k+1的最大公共前后缀，所以next[j + 1] = next[j] + 1不再适用，我们只能寻找更短的最大公共前后缀。

这样看来，如果我们能在p0p1…pk-1pk中不断递归索引k = next[k]，找到一个字符pk’，也是D的话，那么最大公共前后缀长度就为k’+1。此时pk’=pj，且p0p1…pk’-1pk’ = pj-k’pj-k’+1…pj-1pj。从而next[j+1] = k’ + 1 = next[k’] + 1。否则前缀没有D，next[j+1] = 0。
问题（3）已解决

（4）为什么递归前缀索引k = next[k]，就能找到长度更短的相同前缀后缀呢？？？我们用这张图来分析：

在pk != pj时，k = next[k]，用pnext[k]去跟pj继续匹配。为什么不用其他值和pj匹配呢？我们可以看到，在pj之前，有一段长度为k的已匹配串；在pk之前有一段蓝色的已匹配串，说明pk字符前有一段长度为next[k]的最大公共前后缀（蓝色的那段）。如果pk != pj，说明p0p1…pk-1pk != pj-kpj-k+1…pj-1pj，那么我们只能找更短的最大公共前后缀，此时因为pk和pnext[k]前面的蓝色串已完全匹配，如果pnext[k]能和pj匹配 ，那么我们便找到了我们需要的串。如果还是不匹配，下一步pnext[next[k]…]去跟pj继续匹配,直到找到长度更短公共前后缀。
问题（4）已解决
综上，我们可以写出求next数组的递推代码：

void GetNext(char T[])
{
    int j=0,k=-1;
    next[j]=k;
    while(T[j]!='\0')
    {
        if(k==-1||T[j]==T[k])
        {
            j++;
            k++;
            next[j]=k;
        }
        else k=next[k];
    }
}

其实，我们在分析的过程中可以发现，k=next[next[k]…]这一步其实非常的类似于递归。因此我们也给出递归的代码供读者参考。

int GetNext(int j,char T[])
{
    if(j==0)return -1;
    if(j>0)
    {
        int k=GetNext(j-1,T);
        while(k>=0)
        {
            if(T[j-1]==T[k])return k+1;
            else k=GetNext(k,T);
        }
        return 0;
    }
    return 0;
}