一、前缀表：

是用来回退的，它记录了模式串与主串(文本串)不匹配的时候，模式串应该从哪里开始重新匹配。记录下标i之前（包括i）的字符串中，有多大长度的相同前缀后缀。

为什么使用前缀表？

因为找到了最长相等的前缀和后缀，匹配失败的位置是后缀子串的后面，那么我们找到与其相同的前缀的后面从新匹配就可以了。

二、KMP思想：

当出现字符串不匹配时，可以记录一部分之前已经匹配的文本内容，利用这些信息避免从头再去做匹配。

算法细节：

遇到不匹配字母的时候，回退到最大相等前缀的后一个字母开始重新匹配。

如何计算前缀表：

 模式串与前缀表对应位置的数字表示的就是：下标i之前（包括i）的字符串中，有多大长度的相同前后缀。例如aabaa的最大相同前后缀是aa，长度为2，所以前缀表下标4位置的值为2.

找到不匹配的位置时， 我们要看不匹配位置的前一个字符的前缀表的数值是多少。为什么要前一个字符的前缀表的数值呢，因为要找前面字符串的最长相同的前缀和后缀。所以要看前一位的 前缀表的数值。前一个字符的前缀表的数值是2， 所以把下标移动到模式串下标2的位置继续比配。

next数组

next数组就可以是前缀表，但是很多实现都是把前缀表统一减一（右移一位，初始位置为-1）之后作为next数组。

构造next数组：

其实就是计算模式串s，前缀表的过程。 主要有如下三步：

1. 初始化
2. 处理前后缀不相同的情况
3. 处理前后缀相同的情况

class Solution {  // 使用next数组
    public void getNext(int[] next, String s){
        int j = -1;
        next[0] = j;
        for (int i = 1; i < s.length(); i++){  //构建next数组
            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;
        }
    }
    public int strStr(String haystack, String needle) {
        if(needle.length() == 0){
            return 0;
        }
        int[] next = new int[needle.length()];
        getNext(next, needle);
        int j = -1;
        for(int i = 0; i < haystack.length(); i++){
            while(j >= 0 && haystack.charAt(i) != needle.charAt(j + 1)){  //字符不同时，j回退到next[j]
                j = next[j];
            }
            if(haystack.charAt(i) == needle.charAt(j + 1)){  //字符相同时
                j++;
            }
            if(j == needle.length() - 1){  //判断是否匹配成功
                return (i - needle.length() + 1);  //返回在文本串中第一次发现needle的数组下标
            }
        }
        return -1;  //匹配失败
    }
}