java中字符串匹配算法 - 面试宝典
【摘要】 在Java中，常见的字符串匹配算法包括以下几种：朴素模式匹配算法（Naive String Matching Algorithm）：也称为暴力匹配算法，通过逐个比较主串和模式串的字符来进行匹配。时间复杂度为O(m*n)，其中m为主串的长度，n为模式串的长度。KMP算法（Knuth-Morris-Pratt Algorithm）：通过预处理模式串，构建部分匹配表（Partial Match T...
在Java中，常见的字符串匹配算法包括以下几种：
- 朴素模式匹配算法（Naive String Matching Algorithm）：也称为暴力匹配算法，通过逐个比较主串和模式串的字符来进行匹配。时间复杂度为O(m*n)，其中m为主串的长度，n为模式串的长度。
- KMP算法（Knuth-Morris-Pratt Algorithm）：通过预处理模式串，构建部分匹配表（Partial Match Table），在匹配过程中根据部分匹配表进行跳跃式匹配，避免不必要的字符比较。时间复杂度为O(m+n)，其中m为主串的长度，n为模式串的长度。
- Boyer-Moore算法：通过预处理模式串，构建好后缀表（Good Suffix Table）和坏字符表（Bad Character Table），在匹配过程中根据好后缀表和坏字符表进行跳跃式匹配，提高匹配效率。时间复杂度为O(m*n)，但在实际应用中通常比KMP算法更快。
- Rabin-Karp算法：利用哈希函数计算主串中长度为模式串长度的子串的哈希值，并与模式串的哈希值进行比较，如果相等，则进一步比较子串和模式串的每个字符。时间复杂度为O((m-n+1)*n)，其中m为主串的长度，n为模式串的长度。 这些算法在实际应用中有不同的优劣势，适用于不同的场景。可以根据具体需求和数据规模选择合适的字符串匹配算法。
以下是Java中几种字符串匹配算法的示例代码：
- 朴素模式匹配算法：
javaCopy codepublic class NaiveStringMatching {
public static void naiveMatch(String text, String pattern) {
int n = text.length();
int m = pattern.length();
for (int i = 0; i <= n - m; i++) {
int j;
for (j = 0; j < m; j++) {
if (text.charAt(i + j) != pattern.charAt(j))
break;
}
if (j == m)
System.out.println("Pattern found at index " + i);
}
}
public static void main(String[] args) {
String text = "ABABDABACDABABCABAB";
String pattern = "ABABCABAB";
naiveMatch(text, pattern);
}
}- KMP算法：
javaCopy codepublic class KMPStringMatching {
public static void kmpMatch(String text, String pattern) {
int n = text.length();
int m = pattern.length();
int[] lps = computeLPSArray(pattern);
int i = 0, j = 0;
while (i < n) {
if (text.charAt(i) == pattern.charAt(j)) {
i++;
j++;
}
if (j == m) {
System.out.println("Pattern found at index " + (i - j));
j = lps[j - 1];
} else if (i < n && text.charAt(i) != pattern.charAt(j)) {
if (j != 0)
j = lps[j - 1];
else
i++;
}
}
}
private static int[] computeLPSArray(String pattern) {
int m = pattern.length();
int[] lps = new int[m];
int len = 0;
int i = 1;
while (i < m) {
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";
kmpMatch(text, pattern);
}
}- Boyer-Moore算法：
javaCopy codepublic class BoyerMooreStringMatching {
private static final int NO_OF_CHARS = 256;
public static void boyerMooreMatch(String text, String pattern) {
int n = text.length();
int m = pattern.length();
int[] badChar = new int[NO_OF_CHARS];
badCharHeuristic(pattern, m, badChar);
int s = 0;
while (s <= (n - m)) {
int j = m - 1;
while (j >= 0 && pattern.charAt(j) == text.charAt(s + j))
j--;
if (j < 0) {
System.out.println("Pattern found at index " + s);
if (s + m < n)
s += m - badChar[text.charAt(s + m)];
else
s += 1;
} else {
s += Math.max(1, j - badChar[text.charAt(s + j)]);
}
}
}
private static void badCharHeuristic(String pattern, int m, int[] badChar) {
for (int i = 0; i < NO_OF_CHARS; i++)
badChar[i] = -1;
for (int i = 0; i < m; i++)
badChar[pattern.charAt(i)] = i;
}
public static void main(String[] args) {
String text = "ABABDABACDABABCABAB";
String pattern = "ABABCABAB";
boyerMooreMatch(text, pattern);
}
}这些示例代码展示了朴素模式匹配算法、KMP算法和Boyer-Moore算法的实现。可以根据需要使用适当的算法来进行字符串匹配。
【版权声明】本文为华为云社区用户原创内容，转载时必须标注文章的来源（华为云社区）、文章链接、文章作者等基本信息， 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）