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,将匹配的起始位置添加到结果列表中。