KMP算法是用作字符串匹配上的，其主要目的是在匹配的时候如果发现文本串和模式串不同时不需要从头开始匹配，大大减小了时间复杂度。
最长公共前后缀
前缀：是指不包含最后一个字符的所有以第一个字符开头的连续子串。
后缀：后缀是指不包含第一个字符的所有以最后一个字符结尾的连续子串。
最长公共前后缀见名思意
前缀表
将指针从模式串（要去匹配的字符，相对于被匹配的字符串（文本串））第一个字符开始向后移动，直到指向最后一个字符。
指针所在处字符以及指针之前所有字符组成的串 具有一个最长公共前后缀。
前缀表就是在指针移动过程中所有最长公共前后缀组成的数组。
运用前缀表 实现 减小匹配次数
可见在匹配的过程中，文本串的指针不后退；
当匹配到b和f时发现不同，模式串并没有从头开始匹配，而是直接跳到索引为next[j-1]处继续。
next数组(前缀表)的构造—不减1
private void getNext(int[] next, String s) {
int j = 0;
next[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))
j++;
next[i] = j;
}
}
leetcode 28题
实现 strStr() 函数。
给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0 开始）。如果不存在，则返回 -1 。
说明：
当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。
对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与 C 语言的 strstr() 以及 Java 的 indexOf() 定义相符。
示例 1：
输入：haystack = "hello", needle = "ll"
输出：2
示例 2：
输入：haystack = "aaaaa", needle = "bba"
输出：-1
解答
class Solution {
//前缀表（不减一）Java实现
public int strStr(String haystack, String needle) {
if (needle.length() == 0) return 0;
int[] next = new int[needle.length()];
//获取模式串的前缀表
getNext(next, needle);
int j = 0;
for (int i = 0; i < haystack.length(); i++) {
//直到找到第一处的匹配，不匹配时j回退到索引为next[j-1]处
while (j > 0 && needle.charAt(j) != haystack.charAt(i))
j = next[j - 1];
如果匹配一对字符，j向后移
if (needle.charAt(j) == haystack.charAt(i))
j++;
//如果j移动到了模式串的最后，说明全部匹配完成
//返回对应开始的i
if (j == needle.length())
return i - needle.length() + 1;
}
return -1;
}
private void getNext(int[] next, String s) {
int j = 0;
next[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))
j++;
next[i] = j;
}
}
}