KMP算法中next数组的求解

大家既然专门过来查看next数组，说明已经大致了解，kmp算法的运行机制 那接下来，next数组的理解交由我

本文分为四部分：

1. 背景
2. next数组的作用
3. next的定义与构造
4. 代码实现

1. 背景

• 字符串匹配问题
  • KMP诞生于，在文本中找到模式串的背景中
  • 运用双重for循环会大量浪费时间与空间，由此引入kmp，而kmp中next数组就是核心

2.next数组的作用

• 作用
  • next数组的作用为，在遇到不匹配的数组时，进行回退
  • 避免了大量，无意义的比较

3.next的定义与构造

• 说到这里，我就先引入最长公共前后缀，最大公共前后缀是由最长前缀与最长后缀组成。

- - - 最大公共前后缀

• 那大家可能不理解前缀与后缀的概念，我举个例子来解释下
• 前缀：不包含字符串自身的，所有从第一个字符开始的，由前向后所有字符串。
• 后缀：不包含字符串自身的，所有从最后一个字符开始的，由后向前所有字符串。

举例：ababa 所有前缀：a、ab、aba、abab、不包含ababa 所有后置：a、ba、aba、baba、不包含ababa 前缀与后缀拥有相同的字符串、也就是公共字符串有a与aba，但aba长度为3，故aba同时是前缀也是后缀，故aba就是最大公共前后缀

- - - next数组

• 了解完了公共前后缀，这时，距离next数组的求解就近在咫尺。
• 在kmp中，求next数组的对象是，文本串与模式串中的模式串

举例: 一道题中，文本串为ababababf，模式串为ababf、求ababf对应的next数组

这是我画的一张图

这里，我把ababf对应的next数组画了出来，其实，next数组中，每个索引对应的是相应的字符个数。 例如ab前缀a，后缀b。最大公共前后缀为0 abab前缀a、ab、aba，后缀b、ab、bab,最大公共前后缀为ab,故为2。由此得出下表。

结果表

本图最下方一排，就为next数组对应的数据，至于为何？是为了方便kmp匹配用。

4、代码-具体实现

C++

C++写法
void getNext(int* next, const string& s){
    int j = -1;
    next[0] = j;
    for(int i = 1; i < s.size(); i++) { // 注意i从1开始
        while (j >= 0 && s[i] != s[j + 1]) { // 前后缀不相同了
            j = next[j]; // 向前回退
        }
        if (s[i] == s[j + 1]) { // 找到相同的前后缀
            j++;
        }
        next[i] = j; // 将j（前缀的长度）赋给next[i]
    }
}

Java

java写法
    public void getNext(int[] next, String s){
        int j = -1;
        next[0] = j;
        for (int i = 1; i < s.length(); i++){
            while(j >= 0 && s.charAt(i) != s.charAt(j+1)){
                j=next[j];
            }

            if(s.charAt(i) == s.charAt(j+1)){
                j++;
            }
            next[i] = j;
        }
    }

终于，大功告成，如果大家，有什么疑问以及建议，评论区留言。

给大家推荐个KMP写的很好的博客;，虽然我第一遍咋看明白，但后来受益匪浅

再见。