一、KMP算法基础介绍
大家在编程的时候，经常会遇到在一个长字符串里找一个短字符串的情况，这就是字符串匹配问题。KMP算法就是专门解决这个问题的，它能让我们找起来更快，不用像普通方法那样一个一个字符去比对。
举个例子，假如有一个长字符串 str1 = "ABCDABCDABCD"，我们要在里面找短字符串 str2 = "ABCDABC"。要是用普通的方法，就会从 str1 的第一个字符开始，一个一个和 str2 比对，一旦发现不一样，就从 str1 的下一个字符重新开始比对。这样做效率很低，因为很多字符其实之前已经比对过了。
而KMP算法就聪明多了，它会利用已经比对过的信息，避免重复比对。它的核心就是构建一个 next 数组，这个数组能告诉我们在比对失败的时候，短字符串应该往后移动多少位。
二、传统构建next数组的方法
1. 原理
传统构建 next 数组的方法，就是对于短字符串的每一个位置，找出它前面的子串中，前缀和后缀相同的最长长度。
比如说，对于字符串 str = "ABCDABC"，我们来看看怎么构建 next 数组。
- 当位置
i = 0时，前面没有子串，所以next[0] = 0。 - 当位置
i = 1时，子串是"A"，没有前缀和后缀，所以next[1] = 0。 - 当位置
i = 2时，子串是"AB"，前缀是"A"，后缀是"B"，不相同，所以next[2] = 0。 - 当位置
i = 3时，子串是"ABC"，前缀是"A"、"AB"，后缀是"C"、"BC"，不相同，所以next[3] = 0。 - 当位置
i = 4时，子串是"ABCD"，前缀是"A"、"AB"、"ABC"，后缀是"D"、"CD"、"BCD"，不相同，所以next[4] = 0。 - 当位置
i = 5时，子串是"ABCDA"，前缀是"A"、"AB"、"ABC"、"ABCD"，后缀是"A"、"DA"、"CDA"、"BCDA"，最长相同的是"A"，长度为 1，所以next[5] = 1。 - 当位置
i = 6时，子串是"ABCDAB"，前缀是"A"、"AB"、"ABC"、"ABCD"、"ABCDA"，后缀是"B"、"AB"、"DAB"、"CDAB"、"BCDAB"，最长相同的是"AB"，长度为 2，所以next[6] = 2。
2. 代码示例（Java）
// Java 技术栈
public class KMPNextArray {
public static int[] getNext(String pattern) {
int m = pattern.length();
int[] next = new int[m];
int j = 0;
for (int i = 1; i < m; i++) {
// 当不匹配时，回溯 j 的位置
while (j > 0 && pattern.charAt(i) != pattern.charAt(j)) {
j = next[j - 1];
}
if (pattern.charAt(i) == pattern.charAt(j)) {
j++;
}
next[i] = j;
}
return next;
}
public static void main(String[] args) {
String pattern = "ABCDABC";
int[] next = getNext(pattern);
for (int i = 0; i < next.length; i++) {
System.out.print(next[i] + " ");
}
}
}
在这个代码里，getNext 方法就是用来构建 next 数组的。i 表示当前位置，j 表示前缀和后缀相同的长度。当 pattern.charAt(i) 和 pattern.charAt(j) 不相等时，就通过 next[j - 1] 回溯 j 的位置，直到相等或者 j 为 0。
三、构建next数组的优化方法
1. 原理
传统的 next 数组构建方法有个小问题，就是在某些情况下会做一些不必要的回溯。比如说，当 pattern[i] 和 pattern[j] 不相等，回溯到 next[j - 1] 后，发现 pattern[next[j - 1]] 还是和 pattern[i] 不相等，这样就又要继续回溯。
优化的方法就是在构建 next 数组的时候，直接跳过这些不必要的回溯。具体做法是，当 pattern[i] 和 pattern[j] 不相等，回溯到 next[j - 1] 后，如果 pattern[next[j - 1]] 和 pattern[i] 还是不相等，就继续回溯，直到找到一个相等的位置或者 j 为 0。
2. 代码示例（Java）
// Java 技术栈
public class KMPOptimizedNextArray {
public static int[] getOptimizedNext(String pattern) {
int m = pattern.length();
int[] next = new int[m];
int j = 0;
for (int i = 1; i < m; i++) {
while (j > 0 && pattern.charAt(i) != pattern.charAt(j)) {
j = next[j - 1];
}
if (pattern.charAt(i) == pattern.charAt(j)) {
j++;
}
// 优化部分
if (j > 0 && pattern.charAt(i + 1) == pattern.charAt(j)) {
next[i] = next[j - 1];
} else {
next[i] = j;
}
}
return next;
}
public static void main(String[] args) {
String pattern = "ABCDABC";
int[] next = getOptimizedNext(pattern);
for (int i = 0; i < next.length; i++) {
System.out.print(next[i] + " ");
}
}
}
在这个代码里，getOptimizedNext 方法就是优化后的构建 next 数组的方法。当 pattern.charAt(i + 1) 和 pattern.charAt(j) 相等时，就把 next[i] 设为 next[j - 1]，这样就跳过了不必要的回溯。
四、优化方法的实践应用
1. 字符串匹配
在实际的字符串匹配中，使用优化后的 next 数组能让匹配速度更快。比如说，我们要在长字符串 str1 = "ABCDABCDABCD" 里找短字符串 str2 = "ABCDABC"。
// Java 技术栈
public class KMPMatching {
public static int kmpSearch(String text, String pattern) {
int n = text.length();
int m = pattern.length();
int[] next = getOptimizedNext(pattern);
int j = 0;
for (int i = 0; i < n; i++) {
while (j > 0 && text.charAt(i) != pattern.charAt(j)) {
j = next[j - 1];
}
if (text.charAt(i) == pattern.charAt(j)) {
j++;
}
if (j == m) {
return i - m + 1;
}
}
return -1;
}
public static int[] getOptimizedNext(String pattern) {
int m = pattern.length();
int[] next = new int[m];
int j = 0;
for (int i = 1; i < m; i++) {
while (j > 0 && pattern.charAt(i) != pattern.charAt(j)) {
j = next[j - 1];
}
if (pattern.charAt(i) == pattern.charAt(j)) {
j++;
}
if (j > 0 && pattern.charAt(i + 1) == pattern.charAt(j)) {
next[i] = next[j - 1];
} else {
next[i] = j;
}
}
return next;
}
public static void main(String[] args) {
String text = "ABCDABCDABCD";
String pattern = "ABCDABC";
int index = kmpSearch(text, pattern);
if (index != -1) {
System.out.println("Pattern found at index: " + index);
} else {
System.out.println("Pattern not found");
}
}
}
在这个代码里，kmpSearch 方法就是用优化后的 next 数组进行字符串匹配的。当 j 等于 m 时，说明找到了匹配的字符串，返回匹配的起始位置。
2. 生物信息学
在生物信息学里，经常要在 DNA 序列里找特定的基因片段，这其实也是字符串匹配问题。使用优化后的 KMP 算法能提高查找效率。比如说，有一个 DNA 序列 dna = "ATCGATCGATCG"，要找基因片段 gene = "ATCG"。
// Java 技术栈
public class BioinformaticsKMP {
public static int kmpSearch(String dna, String gene) {
int n = dna.length();
int m = gene.length();
int[] next = getOptimizedNext(gene);
int j = 0;
for (int i = 0; i < n; i++) {
while (j > 0 && dna.charAt(i) != gene.charAt(j)) {
j = next[j - 1];
}
if (dna.charAt(i) == gene.charAt(j)) {
j++;
}
if (j == m) {
return i - m + 1;
}
}
return -1;
}
public static int[] getOptimizedNext(String pattern) {
int m = pattern.length();
int[] next = new int[m];
int j = 0;
for (int i = 1; i < m; i++) {
while (j > 0 && pattern.charAt(i) != pattern.charAt(j)) {
j = next[j - 1];
}
if (pattern.charAt(i) == pattern.charAt(j)) {
j++;
}
if (j > 0 && pattern.charAt(i + 1) == pattern.charAt(j)) {
next[i] = next[j - 1];
} else {
next[i] = j;
}
}
return next;
}
public static void main(String[] args) {
String dna = "ATCGATCGATCG";
String gene = "ATCG";
int index = kmpSearch(dna, gene);
if (index != -1) {
System.out.println("Gene found at index: " + index);
} else {
System.out.println("Gene not found");
}
}
}
在这个代码里，kmpSearch 方法就是在 DNA 序列里找基因片段的。通过优化后的 next 数组，能更快地找到匹配的基因片段。
五、技术优缺点
1. 优点
- 效率高：KMP 算法本身就比普通的字符串匹配算法效率高，优化后的
next数组能进一步提高效率，减少不必要的回溯。 - 稳定性好：无论字符串的长度和内容如何，KMP 算法的时间复杂度都是 $O(n + m)$，其中 $n$ 是长字符串的长度，$m$ 是短字符串的长度。
2. 缺点
- 空间复杂度较高：需要额外的空间来存储
next数组，对于非常长的字符串，可能会占用较多的内存。 - 实现复杂：KMP 算法本身就比较复杂，优化后的
next数组构建方法更复杂，对于初学者来说可能不太容易理解。
六、注意事项
1. 边界条件
在构建 next 数组和进行字符串匹配时，要注意边界条件。比如说，当 j 为 0 时，就不能再回溯了。
2. 数组越界
在代码里，要注意数组越界的问题。比如说，在判断 pattern.charAt(i + 1) 时，要确保 i + 1 不会超出数组的范围。
3. 性能测试
在实际应用中，要对优化后的 KMP 算法进行性能测试，确保它确实能提高效率。可以使用不同长度和内容的字符串进行测试，比较优化前后的运行时间。
七、文章总结
KMP 算法是一种非常实用的字符串匹配算法，通过构建 next 数组能避免不必要的回溯，提高匹配效率。而优化后的 next 数组构建方法，能进一步减少回溯，让匹配速度更快。
在实际应用中，KMP 算法可以用于字符串匹配、生物信息学等领域。不过，它也有一些缺点，比如空间复杂度较高、实现复杂等。在使用时，要注意边界条件、数组越界等问题，并且要进行性能测试，确保优化后的算法确实能提高效率。
评论