KMP算法理解

文章大纲：
1.KMP算法概念
2.KMP算法中最核心的next[] 数组是如何生成的
3.使用KMP算法 匹配字符串 java实现
4.再次梳理记忆和理解KMP算法

KMP算法概念：

假设现在我们面临这样一个问题：有一个文本串S，和一个模式串P，现在要查找P在S中的位置，怎么查找呢？
如果用暴力匹配的思路，并假设现在文本串S匹配到 i 位置，模式串P匹配到 j 位置，则有：
如果当前字符匹配成功（即S[i] == P[j]），则i++，j++，继续匹配下一个字符；
如果失配（即S[i]! = P[j]），令i = i - (j - 1)，j = 0。相当于每次匹配失败时，i 回溯，j 被置为0。

理清楚了暴力匹配算法的流程及内在的逻辑，咱们可以写出暴力匹配的代码，如下：

<pre>
<code>

• int ViolentMatch(char* s, char* p)
  · {

• int sLen = strlen(s);
  

• int pLen = strlen(p);
  

• int i = 0;
  

• int j = 0;
  

•   while (i < sLen && j < pLen)
  

• {
  

•     if (s[i] == p[j])
  

•     {
  

•         //①如果当前字符匹配成功（即S[i] == P[j]），则i++，j++
  

•         i++;
  

•         j++;
  

•     }
  

•     else
  

•     {
  

•         //②如果失配（即S[i]! = P[j]），令i = i - (j - 1)，j = 0
  

•         i = i - j + 1;
  

•         j = 0;
  

•     }
  

• }
  

• //匹配成功，返回模式串p在文本串s中的位置，否则返回-1
  

• if (j == pLen)
  

•     return i - j;
  

• else
  

•     return -1;
  

• }
  </pre>
  </code>

比如：你看当字符串匹配到这里的时候 此时不匹配了。

按照暴力的方法 上面一串将回到第5个位置 下面那一串回到0位置进行重新比较。

此时肯定是不匹配的，因为在前面的匹配过程中 已经按照顺序匹配成功才会走到最后D位置　，由此可以推理得到第一个A肯定不能和它的下一个也就是B相匹配。

ＫＭＰ算法就是 利用之前已经部分匹配这个有效信息，保持i（大串的坐标） 不回溯，通过修改j（待匹配串的坐标） 的位置，让模式串尽量地移动到有效的位置。

整个的算法流程：

假设现在文本串S匹配到 i 位置，模式串P匹配到 j 位置
如果j = -1，或者当前字符匹配成功（即S[i] == P[j]），都令i++，j++，继续匹配下一个字符；
如果j != -1，且当前字符匹配失败（即S[i] != P[j]），则令 i 不变，j = next[j]。此举意味着失配时，模式串P相对于文本串S向右移动了j - next [j] 位。
换言之，当匹配失败时，模式串向右移动的位数为：失配字符所在位置 - 失配字符对应的next 值（next 数组的求解会在下文的3.3.3节中详细阐述），即移动的实际位数为：j - next[j]，且此值大于等于1。
<pre>
<code>

/**

• 匹配相应的字符串 Kmp
• @param a 总字符串
• @param b 待匹配字符串
• @return 匹配成功返回 字符串在总串中的起始位置 失败返回-1
  */

int Kmpsearch(String a,String b){

char [] chars_1=a.toCharArray();
char [] chars_2=b.toCharArray();

int len_1=a.length();
int len_2=b.length();
this.next=getNext(b);//根据b要匹配的串 生成相应的next数组
int i=0,j=0;
while (i<len_1&&j<len_2){
    if (j==-1||chars_1[i]==chars_2[j]){
        i++;
        j++;
    }else {
        j=next[j];
    }
}
if (j==len_2){
    return i-j;
}else {
    return -1;
}

</pre>
</code>

接下来我们就只需要去考虑如何生成next数组即可

KMP算法中最核心的next[] 数组是如何生成的：

我们先来假设一下next[j]=k 那么这是什么意思呢？
意思就是在第j个位置之前的所有字符串中存在前缀后缀相等的字符串长度为k，所以如果当你匹配到第j个位置是匹配失败，那么你直接使用next去求得k位置重新进行和总字符串这个同一位置比较时，就把前面相同匹配过的过程给节约了。因为你的前后缀相同。如果解释不明白，后面还会有图帮助理解。

下面这张图是来理解前缀后缀的概念：

我们用一个网上的例子进行讲解next的生成：

如下图所示，假定给定模式串ABCDABCE，且已知next [j] = k（上面说过这个的含义 那么在这里 我们可以看到就是Pj之前 ABCDAB的最大相同前后缀为AB 也就是k=2），现要求next [j + 1]等于多少？因为pk = pj = C，所以next[j + 1] = next[j] + 1 = k + 1（可以看出next[j + 1] = 3）。代表字符E前的模式串中，有长度k+1 的相同前缀后缀。

但如果pk != pj 呢？说明“p0 pk-1 pk” ≠ “pj-k pj-1 pj”。换言之，当pk != pj后，字符E前有多大长度的相同前缀后缀呢？很明显，因为C不同于D，所以ABC 跟 ABD不相同，即字符E前的模式串没有长度为k+1的相同前缀后缀，也就不能再简单的令：next[j + 1] = next[j] + 1 。所以，咱们只能去寻找长度更短一点的相同前缀后缀。

用什么方法去寻找更短一点的相同前后缀呢？
递归前缀索引k = next[k]，就能找到长度更短的相同前缀后缀 。这又归根到next数组的含义。我们拿前缀 p0 pk-1 pk 去跟后缀pj-k pj-1 pj匹配，如果pk 跟pj 失配，下一步就是用p[next[k]] 去跟pj 继续匹配，如果p[ next[k] ]跟pj还是不匹配，则需要寻找长度更短的相同前缀后缀，即下一步用p[ next[ next[k] ] ]去跟pj匹配。此过程相当于模式串的自我匹配，所以不断的递归k = next[k]，直到要么找到长度更短的相同前缀后缀，要么没有长度更短的相同前缀后缀。如下图所示：

这幅图一开始我也没太认真去看，觉得有点复杂。后面仔细想了一下回过头再看确实对理解k=next[k]有很大的帮助

我的个人理解是这样的：
首先我们可以看到Pj位置，前面有两块相同的k块，在图片上方用大括号括起来代表相同的前后缀长度为k 用公式表示就是next[j]=k ，
然后此时Pk和Pj不相同。一块红色一块黄色。我们要去寻找短的前缀，
根据k=next[k]我们到了Pnext[k]位置 也就是Pk前面存在的最大相同前缀。
看前半部分，是两块蓝色的相等部分。然后此时去比较Pnext[k]和Pj看是否相同，如果相同就有next[j+1]=next[k]+1,
那么为什么j+1的位置前面会有next[k]+1的相同前后缀呢。我们看图，两块k区域是相等的，然后Pk前面的两块蓝色是相等的，所以四块蓝色的区域也就相等了。
那么P0到Pnext[k]这一块也就和Pj相邻的蓝色块相等。
如果一直找到头都没有短一点的前后缀，则next[j+1]=0

现在我们再总结一下next数组的生成，假设：next[j]=k 那么next[j+1]根据Pk和Pj是否相同有两种情况，如果相同 则next[j+1]=k+1,如果不相同则k=next[k]继续去判断此时的Pk和Pj是否相同。
我们初始化化赋值为 j=0 k=-1 next[0]=-1 下面用代码写一遍：
<pre>
<code>

/**

• 获取next数组的函数
• @param string 模式串 待匹配的字符串
• @return 生成的next函数
  */

public int [] getNext(String string){

char [] chars=string.toCharArray();
int len=string.length();
int k=-1;
int j=0;
int []next=new int[len];
next[0]=-1;
while (j<len-1){
    if (k==-1||chars[j]==chars[k]){//chars[j]前缀 chars[k]后缀 相等 或者k==-1
       next[++j]=++k;
    }else {
        k=next[k];//当不匹配时 去前面最大匹配的位置那再次进行比较看是否能匹配
    }
}
return next;

}

</pre>
</code>

next数组优化

如果用之前的next 数组方法求模式串“abab”的next 数组，可得其next 数组为-1 0 0 1，当它跟下图中的文本串去匹配的时候，发现b跟c失配，于是模式串右移j - next[j] = 3 - 1 =2位。

右移2位后，b又跟c失配。事实上，因为在上一步的匹配中，已经得知p[3] = b，与s[3] = c失配，而右移两位之后，让p[ next[3] ] = p[1] = b 再跟s[3]匹配时，必然失配。问题出在哪呢？

问题出在不该出现p[j] = p[ next[j] ]。为什么呢？理由是：当p[j] != s[i] 时，下次匹配必然是p[ next [j]] 跟s[i]匹配，如果p[j] = p[ next[j] ]，必然导致后一步匹配失败（因为p[j]已经跟s[i]失配，然后你还用跟p[j]等同的值p[next[j]]去跟s[i]匹配，很显然，必然失配），所以不能允许p[j] = p[ next[j ]]。如果出现了p[j] = p[ next[j] ]咋办呢？如果出现了，则需要再次递归，即令next[j] = next[ next[j] ]。

所以，咱们得修改下求next 数组的代码。

<pre>
<code>

/**

• 获取next数组的函数
• @param string 模式串 待匹配的字符串
• @return 生成的next函数
  */

public int [] getNext(String string){

char [] chars=string.toCharArray();
int len=string.length();
int k=-1;
int j=0;
int []next=new int[len];
next[0]=-1;
while (j<len-1){
    if (k==-1||chars[j]==chars[k]){//chars[j]前缀 chars[k]后缀 相等 或者k==-1
        j++;
        k++;
        if (chars[j]!=chars[k]){//如果此时你让 next[j]=k 那么进行位移的时候 把chars[k]拿去匹配还是失败 因为chars[j]已经失败过
            next[j]=k;
        }else {  //因为不能出现p[j] = p[next[j]]，所以当出现时需要继续递归，k = next[k] = next[next[k]]
            next[j]=next[k];
        }
    }else {
        k=next[k];//当不匹配时 去前面最大匹配的位置那再次进行比较看是否能匹配
    }
}
return next;

}

</pre>
</code>

使用KMP算法 匹配字符串 java实现

<pre>
<code>

/**

• 获取next数组的函数
• @param string 模式串 待匹配的字符串
• @return 生成的next函数
  */

public int [] getNext(String string){

char [] chars=string.toCharArray();
int len=string.length();
int k=-1;
int j=0;
int []next=new int[len];
next[0]=-1;
while (j<len-1){
    if (k==-1||chars[j]==chars[k]){//chars[j]前缀 chars[k]后缀 相等 或者k==-1
        j++;
        k++;
        if (chars[j]!=chars[k]){//如果此时你让 next[j]=k 那么进行位移的时候 把chars[k]拿去匹配还是失败 因为chars[j]已经失败过
            next[j]=k;
        }else {  //因为不能出现p[j] = p[next[j]]，所以当出现时需要继续递归，k = next[k] = next[next[k]]
            next[j]=next[k];
        }
    }else {
        k=next[k];//当不匹配时 去前面最大匹配的位置那再次进行比较看是否能匹配
    }
}
return next;

}

/**

• 匹配相应的字符串 Kmp
• @param a 总字符串
• @param b 待匹配字符串
• @return 匹配成功返回 字符串在总串中的起始位置 失败返回-1
  */

int Kmpsearch(String a,String b){

char [] chars_1=a.toCharArray();
char [] chars_2=b.toCharArray();

int len_1=a.length();
int len_2=b.length();
this.next=getNext(b);//根据b要匹配的串 生成相应的next数组
int i=0,j=0;
while (i<len_1&&j<len_2){
    if (j==-1||chars_1[i]==chars_2[j]){
        i++;
        j++;
    }else {
        j=next[j];
    }
}
if (j==len_2){
    return i-j;
}else {
    return -1;
}

}

</pre>
</code>

再次梳理记忆和理解KMP算法

KMP算法的使用过程：两个待比较的字符串进行单个字符一一比较，如果相等则进行下一个位置的比较，否则模式串（小的那串）的位置移动到next[当前位置]。

关键的next数组生成：
有两个指针 j和k。 当k=-1或者在J和K位置的字符相等时，两指针同时向前一位。否则k回退到next[k]位置（寻找更短的前后缀相等位置）。若两指针同时向前一位时 ，比较新的J和K位置字符是否相等，若相等则next[j]=next[k] ，不等 next[j]=k.

文章参考来源：
从头到尾彻底理解KMP