一、前言
查找子串，是字符串查找的经典题目，大学就有！
比如：
主串：『ABAEABDACAADABACDDA』中查找
子串：『ABACD』
不考虑性能（时间、空间复杂度），大家可能就直接用暴力来求解了：Brute-Force（BF）、Back-Track（BT）；但如果要求有一定的性能，那么 KMP 无疑是最经典的算法了（虽然不一定是效率最高的）
二、BF算法
// BF暴力算法
private static int bruteForce(String s, String p) {
int i = 0;
for (; i < s.length() - p.length() + 1; i ++) {
int j = 0;
for (; j < p.length(); j ++) {
if (s.charAt(i + j) == p.charAt(j)) {
continue;
}
break;
}
if (j == p.length()) {
return i;
}
}
return -1;
}
三、BT算法
// BT回溯算法
private static int backTrack(String s, String p) {
int i = 0, j = 0;
while (i < s.length() && j < p.length()) {
if (s.charAt(i) == p.charAt(j)) {
j ++;
} else {
i -= j;
j = 0;
}
i ++;
}
return j == p.length() ? i - j : -1;
}
四、KMP算法
我们先来通过主串与子串的查找来找找规律：
image.png
再来看另一个数据多点的例子：
17084030-82e4b71b85a440c5a636d57503931415.png
『C』与『B』不匹配时，滑动子串，因为，有共同的前缀『AB』，所以，只需要从子串『index = 2』开始比较就行，如下图：
17084037-cc3c34200809414e9421c316ceba2cda.png
至此我们可以大概看出一点端倪，当匹配失败时，j要移动的下一个位置k。
存在着这样的性质：
最前面的k个字符和j之前的最后k个字符是一样的。
如果用数学公式来表示是这样的 ：
P[0 ~ k-1] == P[j-k ~ j-1]
这个相当重要，如果觉得不好记的话，可以通过下图来理解（即 P[j]发生不匹配时，滑动到k的位置，比较P[k]）：
17084056-66930855432b4357bafbf8d6c76c1840.png
主串S 与 子串P 在 j 处发生不匹配时，为什么可以移动到位置 k 推导：
- S[i] != P[j]时，必然存在：S[i-j ~ i-1] == P[0 ~ j-1]；
- P中存在一个k，使得：P[0 ~ k-1] == P[j-k ~ j-1]；
- 那么：S[i-k ~ i-1] = P[0 ~ k-1]
如果求 k ？我们需要借助一个数组，来记录当每个位置发生不匹配时，需要滑动到的位置，如下图：
Next 就是一个记录的数组（前缀数）：
- 初始标记： next[0] = -1；
- next[k] = 相同前缀的字符个数;
-
当 p[j] != p[k] 时， k = next[k] （直观就看下图：『C』和『B』）
imagexxxx.png
// j为不匹配时的下标，k下标对应的是
// 串[0 ~ k-1] = 串[j-k ~ j-1]
private static int[] getNext(String p) {
int next[] = new int[p.length()];
int k = -1, j = 0;
next[0] = -1;
while (j < p.length() - 1) {
if (k == -1 || p.charAt(j) == p.charAt(k)) {
next[++j] = ++k;
} else {
k = next[k]; // next数组中前K个元素，已经有前缀统计
}
}
return next;
}
KMP最终算法如下
// KMP算法
private static int kmp(String s, String p) {
int next[] = getNext(p);
int i = 0, j = 0;
while (i < s.length() && j < p.length()) {
if (j == -1 || s.charAt(i) == p.charAt(j)) {
i ++;
j ++;
} else {
j = next[j];
}
}
return j == p.length() ? i - j : -1;
}
