KMP算法：
- KMP算法，全称为Knuth-Morris-Pratt算法，是一种用于字符串匹配的高效算法。它的主要思想是利用已经匹配过的字符信息，避免不必要的回溯，从而提高匹配的效率。
- KMP算法的核心是构建一个辅助数组next，用来记录模式串中每个字符对应的最长公共前缀和后缀的长度。通过这个数组，可以在匹配过程中根据已匹配的前缀信息，跳过一些不必要的比较。
具体的匹配过程如下：
- 首先，根据模式串构建next数组。next[i]表示模式串中以第i个字符结尾的子串的最长公共前缀和后缀的长度。
- 然后，从文本串的第一个字符开始，与模式串的第一个字符进行比较。
- 如果当前字符匹配成功，则依次比较下一个字符，直到模式串结束或者字符不匹配。
- 如果当前字符匹配失败，则根据next数组的值，移动模式串的位置，继续与文本串中的下一个字符进行比较。
- 如果next[j] = -1，表示模式串需要移动到下一个位置，即i++；
- 如果next[j] ≠ -1，表示模式串需要向右移动的位置为j - next[j]。
KMP算法的时间复杂度为O(m +
n)，其中m为模式串的长度，n为文本串的长度。相比于朴素的字符串匹配算法，KMP算法通过利用已匹配的前缀信息，避免了一些不必要的比较，从而提高了匹配的效率。
public class Kmp {
// 构建next数组
private int[] buildNext(String pattern) {
int[] next = new int[pattern.length()]; // next数组，用于记录最长公共前缀和后缀的长度
int i = 0; // pattern的索引
int j = -1; // next数组的值
next[0] = -1; // 第一个字符的next值为-1
while (i < pattern.length() - 1) {
if (j == -1 || pattern.charAt(i) == pattern.charAt(j)) {
i++;
j++;
next[i] = j;
} else {
j = next[j];
}
}
return next;
}
// KMP算法匹配
public int kmpMatch(String text, String pattern) {
int[] next = buildNext(pattern);
System.out.println("next数组：");
for(int i=0;i<next.length;i++){
if(i==next.length-1){
System.out.print(next[i]+"\n");
}else{
System.out.print(next[i]);
}
}
int i = 0; // text的索引
int j = 0; // pattern的索引
while (i < text.length() && j < pattern.length()) {
if (j == -1 || text.charAt(i) == pattern.charAt(j)) {
i++;
j++;
} else {
j = next[j];
}
}
if (j == pattern.length()) {
return i - j; // 返回匹配的起始位置
} else {
return -1; // 没有匹配的子串
}
}
// 测试
public static void main(String[] args) {
String text = "abbabbababaaababaaababab";//文本串
String pattern = "ababaaababaa";//模式串
Kmp kmp=new Kmp();
int index = kmp.kmpMatch(text, pattern);
if (index != -1) {
System.out.println("在位置 " + index + " 处找到匹配的子串");
} else {
System.out.println("未找到匹配的子串");
}
}
}
解释一下，KMP算法中的next数组的构建部分：
- 首先，创建一个长度为模式串长度的next数组。然后，定义两个指针i和j，分别用于指向模式串中的字符和next数组中的值。
- 接下来，将第一个元素的next值设置为-1，表示没有公共前缀和后缀。
- 然后，使用while循环遍历模式串中的字符，直到遍历到倒数第二个字符。在循环中，判断j的值是否为-1或者当前字符与对应位置的字符相等。
- 如果j的值为-1，表示没有找到公共前缀和后缀，此时将i和j都向后移动一位，并将next[i]的值设置为j。
- 如果当前字符与对应位置的字符相等，表示找到了公共前缀和后缀，此时将i和j都向后移动一位，并将next[i]的值设置为j。
- 如果j的值不为-1且当前字符与对应位置的字符不相等，表示当前字符与j位置处的字符不匹配，需要将j的值更新为next[j]，即回退到之前相同前缀的位置。
- 最后，返回构建好的next数组。
简单地说一下next数组吧：
1、先求模式串每个子串的最长公共前后缀
2、然后看题目要求（有时候你得两种情况都抽一眼）
（1）下标从0开始：将上面求的数组整体右移一位（第一位补-1）
（2）下标从1开始：将第一种情况求得的数组加1
