设有文本串S和模式串P，现在要P是否为S的一个子串，若是，则返回P在S中开始的位置，若不是，返回-1。
思路：我们最先想到的应该就是暴力算法，子串与主串挨个比较，如果不相等则退回，但是这种算法的时间复杂度太高。如果主串有n个字符，子串有m个字符，那么这种算法的时间复杂度达到了O（n*m）。因此我们今天介绍一种时间复杂度更低的KMP（看毛片）算法。
首先我们来看什么是kmp算法，KMP算法就是对子串的前缀和后缀进行匹配，得出一个next数组，通过数组来帮助我们匹配子串和主串。
（注：前缀和后缀的长度不能相等）
KMP算法最重要也是最难理解的就是next数组。
开始时，K的位置在0处，我们人为规定next数组的数值为-1。这时k向后移动在位置1处，这时b前方只有一个字符a，无法分出前缀和后缀，所以此处位置也是认为规定的0。
此时K来到2的位置，发现a，b不相等，所以next数组为0。
接着向后移动a,b不相等，所以next数组为0。
接着移动k，发现a，a相等，所以此时next数组为1。
接着移动k，发现b，b相等，所以此时next数组需要加一变为2。
依次类推写出next数组。
我们在比较子串和主串时，前面都相同，但是d和e显然不同，按照暴力算法的思路，我们会将str2的第一个字符a去和str1第二个字符b去对比，而kmp算法中有一个next数组，它可以帮我们省去很多的步骤。
在str2中在e出的next数组显然是4，说明在srt2中前四个字符与后四个字符是完全相同的。而在str2与str1对比的过程中，在e之前的字符串肯定会与str1的字符串存在相同的序列，所以str1d前面的部分相当于str2e前面的字符串后缀，而str2中e前方的字符串后缀有四个与前面是相同的（也就是next数组的值为4），所以这四个字符串就不需要我们去对比了，可定会相等。
也就是上图中所标记的三个子字符串必定相等，因此就不再需要去比较str1的后缀和str2的前缀，依次来降低时间复杂度。
代码：package Servlet;
public class KMP {
public static void main(String[] args) {
String test = "asdxxcdfdasxczfasdasdxzc";
String pattern = "xxcdfdasxc";
int a = KmpMatch(test, pattern);
if (a == -1) {
System.out.println("字符串不包含");
} else {
System.out.println("字符串在第" + a + "位置被包含");
}
}
public static int[] getNext(char[] str) {
//如果字符数组的长度为1，直接返回元素为-1的数组
if (str.length == 1) {
return new int[]{-1};
}
int[] next = new int[str.length];
next[0] = -1;
next[1] = 0;
int k;
//从第2个位置开始算next数组
for (int i = 2; i < str.length; i++) {
k = next[i - 1];
while (k != -1) {
if (str[i - 1] == str[k]) {//说明i-1位置和k位置匹配上了，可以在原有的前后缀匹配长度上加1
next[i] = k + 1;
break;
} else if (next[k] >= 0) {//比对不上，但可以往前跳，看有没有更小的前后缀匹配可以利用上
k = next[k];
} else {//对比不上了，也没法往前跳，直接复制为0
next[i] = 0;
break;
}
}
}
return next;
}
public static int KmpMatch(String text, String pattern) {
//判断极端条件
if (text == null || pattern == null || pattern.length() < 1 || text.length() < 1) {
return -1;
}
char[] str1 = text.toCharArray();
char[] str2 = pattern.toCharArray();
int i = 0, j = 0;
//得到next数组
int[] next = getNext(str2);
while (i < str1.length && j < str2.length) {
if (j == -1 || str1[i] == str2[j]) {
i++;
j++;
} else {
j = next[j];
}
}
if (j == str2.length) {
return i - j + 1;
} else {
return -1;
}
}
}
代码参考于KMP算法详解_哔哩哔哩_bilibili
