详解参考： KMP算法讲解
next 数组求法
方式1
移动位数 = 已匹配的字符数 - 对应的部分匹配值
已知空格与D不匹配时，前面六个字符"ABCDAB"是匹配的。查表可知，最后一个匹配字符B对应的"部分匹配值"为2，因此按照下面的公式算出向后移动的位数：
移动位数 = 已匹配的字符数 - 对应的部分匹配值
因为 6 - 2 等于4，所以将搜索词向后移动4位。
因为空格与Ｃ不匹配，搜索词还要继续往后移。这时，已匹配的字符数为2（"AB"），对应的"部分匹配值"为0。所以，移动位数 = 2 - 0，结果为 2，于是将搜索词向后移2位。
"前缀"和"后缀"。 "前缀"指除了最后一个字符以外，一个字符串的全部头部组合；"后缀"指除了第一个字符以外，一个字符串的全部尾部组合。
"部分匹配值"就是"前缀"和"后缀"的最长的共有元素的长度。以"ABCDABD"为例，
－ "A"的前缀和后缀都为空集，共有元素的长度为0；
－ "AB"的前缀为[A]，后缀为[B]，共有元素的长度为0；
－ "ABC"的前缀为[A, AB]，后缀为[BC, C]，共有元素的长度0；
－ "ABCD"的前缀为[A, AB, ABC]，后缀为[BCD, CD, D]，共有元素的长度为0；
－ "ABCDA"的前缀为[A, AB, ABC, ABCD]，后缀为[BCDA, CDA, DA, A]，共有元素为"A"，长度为1；
－ "ABCDAB"的前缀为[A, AB, ABC, ABCD, ABCDA]，后缀为[BCDAB, CDAB, DAB, AB, B]，共有元素为"AB"，长度为2；
－ "ABCDABD"的前缀为[A, AB, ABC, ABCD, ABCDA, ABCDAB]，后缀为[BCDABD, CDABD, DABD, ABD, BD, D]，共有元素的长度为0。
- 解决指针不回溯
public class Main {
public static void main(String[] args) {
String s="abaabcba";
char[] array = s.toCharArray();
int i = s.length();
// System.out.println(Arrays.toString(getNext(s)));
System.out.println(kmpSearch("ababcddbut","cd"));
}
/**
* O(m+n)
* @param s 目标串
* @param p 模式串
* @return 如果匹配成功，返回下标，否则返回-1
*/
private static int kmpSearch(String s, String p) {
int sLen = s.length();
int pLen = p.length();
if (sLen < pLen) {
return -1;
}
int[] next = getNext(p);
int i = 0, j = 0;
while (i < sLen && j < pLen) {
if (j == -1 || s.charAt(i) == p.charAt(j)) {
i++;
j++;
} else {
j = next[j];
}
}
System.out.println(i+"-----"+j);
return j==pLen?i-j:-1;
}
/**
* k是前缀，i是后缀，如果不等，就k=next[k],前缀往前移
* @param p 匹配串(字串)
* @return
*/
private static int[] getNext(String p) {
int len = p.length();
int[] next = new int[len+1];
next[0] = -1;
int i=0,k=-1;
while (i<len){
if (k==-1||p.charAt(i)==p.charAt(k)){
k++;
i++;
next[i]=k;
}else {
k=next[k];
}
}
return next;
}
}
方式2
- 宫水三叶的解释 力扣地址详解
class Solution {
// KMP 算法
// ss: 原串(string) pp: 匹配串(pattern)
public int strStr(String ss, String pp) {
if (pp.isEmpty()) return 0;
// 分别读取原串和匹配串的长度
int n = ss.length(), m = pp.length();
// 原串和匹配串前面都加空格，使其下标从 1 开始
ss = " " + ss;
pp = " " + pp;
char[] s = ss.toCharArray();
char[] p = pp.toCharArray();
// 构建 next 数组，数组长度为匹配串的长度（next 数组是和匹配串相关的）
int[] next = new int[m + 1];
// 构造过程 i = 2，j = 0 开始，i 小于等于匹配串长度 【构造 i 从 2 开始】
for (int i = 2, j = 0; i <= m; i++) {
// 匹配不成功的话，j = next(j)
while (j > 0 && p[i] != p[j + 1]) j = next[j];
// 匹配成功的话，先让 j++
if (p[i] == p[j + 1]) j++;
// 更新 next[i]，结束本次循环，i++
next[i] = j;
}
// 匹配过程，i = 1，j = 0 开始，i 小于等于原串长度 【匹配 i 从 1 开始】
for (int i = 1, j = 0; i <= n; i++) {
// 匹配不成功 j = next(j)
while (j > 0 && s[i] != p[j + 1]) j = next[j];
// 匹配成功的话，先让 j++，结束本次循环后 i++
if (s[i] == p[j + 1]) j++;
// 整一段匹配成功，直接返回下标
if (j == m) return i - m;
}
return -1;
}
}