KMP算法——解决字符串匹配问题

leedcood 28：实现 strStr() 函数。

给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0 开始）。如果不存在，则返回  -1 。

示例 1：

输入：haystack = "hello", needle = "ll"
输出：2
示例 2：

输入：haystack = "aaaaa", needle = "bba"
输出：-1

字符串在比较失败时，已经知道之前主串和子串都读过哪些字符，避免主串跳回下一个字符重新匹配的步骤（这也是暴力解法的思路）：

  暴力解法思路

KMP算法关键：在当前主串和字串检索过程中，发现不匹配（如主串的A和子串的C），主串不退回，子串都过某种条件移动到与主串A相等的字符上去，再重新比较匹配，如下图

换句话说，在一次遍历主串的过程中找出匹配的子串

这里就需要KMP中定义的next数组，我们先来看怎么利用next数组

KMP算法在匹配失败时，会去看最后一个匹配的字符（例子中的B）所对应的next数值

 此时为2，于是我们移动字串，跳过字串前两个字符

 这里的2代替字串中我们可以跳过匹配的字符个数，即重新开始匹配的子串下标也为2

 重新开始匹配，当子串指针到达末尾，就匹配成功

 public int strStr(String haystack, String needle) {
        
        //得到next数组
        int[] next = new int[needle.length()];
        getNext(next, needle);

        int j = 0; //子串指针
        for (int i = 0; i < haystack.length(); i++) {
            while (j > 0 && needle.charAt(j) != haystack.charAt(i)) 
                j = next[j - 1];  //最后一个匹配的字符所对应的next数值=重新开始匹配的子串下标
            if (needle.charAt(j) == haystack.charAt(i)) 
                j++;
            if (j == needle.length()) 
                return i - needle.length() + 1;
        }
        return -1;

    }

 那么子串的 ABABC 中 0 0 1 2 0 是如何算出来的？

前缀：不包含尾字母的所有字串

以ABABC为例子

前缀有：

A

AB

ABA

ABAB

后缀：不包含头字母的所有字串

以ABABC为例子

后缀有：

B

BA

BAB

BABC

最长相等前后缀：前缀和后缀中最长相等的，以ABABC为例子，子串有五种情况如下

A：没有前缀，也没有后缀，最长相等前后缀0

AB:前缀有A，后缀有B，最长相等前后缀0

ABA：前缀有A，AB,后缀有A，BA，最长相等前后缀1

ABAB:前缀有A，AB，BA，ABA，后缀有B,BA,AB,BAB，最长相等前后缀2

ABABC：前缀A，AB，ABA，ABAB，后缀B，BA，BAB，BABC，最长相等前后缀0

动态规划思想：假设我们已经知道当前共同前后缀，如果下一个字符相等，则最长共同前后缀+1

如果不相等，查看是否有更小共同前后缀，利用左边的最后一个相等下标变成当前长度，重新匹配

private void getNext(int[] next, String s) {
        int j = 0; //最长相等前后缀，数组的值
        next[0] = 0;  //开始为0
        for (int i = 1; i < s.length(); i++) {
            while (j > 0 && s.charAt(j) != s.charAt(i)) //如果不相等，查看更小共同前后缀 
                j = next[j - 1];
            if (s.charAt(j) == s.charAt(i))  //如果下一个字符相等，则最长共同前后缀+1
                j++;
            next[i] = j; 
        }
    }