KMP（Knuth-Morris-Pratt）算法是一种用于在文本中查找子串的线性时间算法。
KMP算法（Knuth-Morris-Pratt算法）是一种字符串匹配算法，用于在一个主文本字符串中查找一个模式字符串的出现位置。
它的主要特点是在匹配过程中，根据已经匹配的部分字符，避免重复的比较，从而实现线性时间复杂度。
算法的名字来源于Donald Knuth、James H. Morris和Vaughan Pratt，他们在1977年发表了这一算法。
KMP算法的核心思想是利用模式字符串自身的信息，提前计算出一个部分匹配表（Partial Match Table），在匹配过程中，根据已经匹配的部分，通过查表来决定下一次比较的位置。这样就避免了一些不必要的比较，提高了匹配的效率。
具体来说，KMP算法的步骤包括：
- 构建部分匹配表（Partial Match Table）： 对于模式字符串，计算它的每个前缀子串（不包括自身）的最长相等前缀后缀的长度，保存在部分匹配表中。
- 匹配过程： 在主文本字符串中，从左到右逐个字符匹配模式字符串。如果发现不匹配，根据部分匹配表决定模式字符串的移动位置。
由于KMP算法的匹配过程中，模式字符串只会按照已经匹配的部分进行移动，不会回退，因此时间复杂度为O(N)，其中N是主文本字符串的长度。KMP算法在字符串匹配中广泛应用，特别是在大数据文本中的模式匹配，或者在实时系统中需要快速匹配的场景中，它的高效性和稳定性使得它成为一种常用的算法。
下面是一个使用Java中的集合和流（Collection和Stream）实现的简单KMP算法：
import java.util.ArrayList;
import java.util.List;
public class KMP {
public static List<Integer> search(String text, String pattern) {
List<Integer> matches = new ArrayList<>();
int[] lps = computeLPSArray(pattern);
int i = 0; // 指向text的指针
int j = 0; // 指向pattern的指针
while (i < text.length()) {
if (text.charAt(i) == pattern.charAt(j)) {
i++;
j++;
}
if (j == pattern.length()) {
matches.add(i - j);
j = lps[j - 1];
} else if (i < text.length() && text.charAt(i) != pattern.charAt(j)) {
if (j != 0) {
j = lps[j - 1];
} else {
i++;
}
}
}
return matches;
}
private static int[] computeLPSArray(String pattern) {
int[] lps = new int[pattern.length()];
int len = 0; // 记录最长匹配的前缀和后缀的长度
int i = 1;
while (i < pattern.length()) {
if (pattern.charAt(i) == pattern.charAt(len)) {
len++;
lps[i] = len;
i++;
} else {
if (len != 0) {
len = lps[len - 1];
} else {
lps[i] = 0;
i++;
}
}
}
return lps;
}
public static void main(String[] args) {
String text = "ABABDABACDABABCABAB";
String pattern = "ABABCABAB";
List<Integer> matches = search(text, pattern);
System.out.println("Text: " + text);
System.out.println("Pattern: " + pattern);
System.out.println("Matches: " + matches);
}
}
|
这个实现中:
- search方法接受文本和模式作为参数，并返回一个包含匹配位置的整数列表。
- computeLPSArray方法用于计算最长前缀和后缀匹配长度的数组。
- 在search方法中，使用了两个指针i和j，其中i指向文本的当前位置，j指向模式的当前位置。
- 根据比较结果，调整指针的位置。当发现匹配时，将匹配的起始位置添加到结果列表中。
正则表达式实现
在Java中使用集合和正则表达式来实现KMP算法的话，可以考虑使用Stream API 来进行一些操作。下面是一个使用Stream API和正则表达式的简单实现：
import java.util.ArrayList;
import java.util.List;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
public class KMPWithStream {
public static List<Integer> search(String text, String pattern) {
List<Integer> matches = new ArrayList<>();
String regex = "(?=(" + Pattern.quote(pattern) + "))";
Pattern compiledPattern = Pattern.compile(regex);
Matcher matcher = compiledPattern.matcher(text);
matcher.results().forEach(matchResult -> {
int start = matchResult.start();
matches.add(start);
});
return matches;
}
public static void main(String[] args) {
String text = "ABABDABACDABABCABAB";
String pattern = "ABABCABAB";
List<Integer> matches = search(text, pattern);
System.out.println("Text: " + text);
System.out.println("Pattern: " + pattern);
System.out.println("Matches: " + matches);
}
}
|
在这个实现中：
- search方法使用正则表达式和Stream API 来查找匹配的位置。
- Pattern.quote方法用于转义模式中的特殊字符，确保正则表达式按照字面意义进行匹配。
- Matcher.results()方法返回一个Stream，其中包含所有匹配的结果。
- 通过遍历Stream，将匹配的起始位置添加到结果列表中。