你熟悉的编程语言中的查找函数，或者工具、软件中的查找功能，都是用了哪种字符串匹配算法呢？
在 Java 编程语言中，字符串的查找函数主要是使用 Brute-Force 算法（朴素字符串匹配算法）或 KMP 算法（Knuth-Morris-Pratt 算法）。这两种算法是常见的字符串匹配算法，各有优劣，具体选择取决于应用场景和需求。
KMP 算法：
KMP 算法是一种改进的字符串匹配算法，它通过预处理模式串，构建一个部分匹配表（Partial Match Table），然后利用这个表来避免在匹配过程中回溯主串的操作。KMP 算法在某些情况下比 Brute-Force 算法更高效，尤其是对于大文本和较长模式串的匹配。
public class KMP { public static int kmpSearch(String text, String pattern) { int[] lps = calculateLPS(pattern); int i = 0, j = 0; while (i < text.length()) { if (pattern.charAt(j) == text.charAt(i)) { i++; j++; } if (j == pattern.length()) { return i - j; } else if (i < text.length() && pattern.charAt(j) != text.charAt(i)) { if (j != 0) { j = lps[j - 1]; } else { i++; } } } return -1; }
private static int[] calculateLPS(String pattern) { int[] lps = new int[pattern.length()]; int len = 0, 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"; int index = kmpSearch(text, pattern); if (index != -1) { System.out.println("Pattern found at index " + index); } else { System.out.println("Pattern not found"); } }}
复制代码
Brute-Force 算法：
也称为朴素字符串匹配算法，它是一种简单直观的字符串匹配算法。它的基本思想是通过两个嵌套循环，在主串中逐个比较子串和模式串的字符，直到找到匹配或者搜索到主串末尾。这是一种最基本的、最容易理解的字符串匹配方法，但在某些情况下可能效率较低，特别是对于长主串和短模式串的匹配。
public class BruteForce { public static int bruteForceSearch(String text, String pattern) { int m = text.length(); int n = pattern.length();
for (int i = 0; i <= m - n; i++) { int j; for (j = 0; j < n; j++) { if (text.charAt(i + j) != pattern.charAt(j)) { break; } } if (j == n) { return i; // Pattern found at index i } } return -1; // Pattern not found }
public static void main(String[] args) { String text = "ABABDABACDABABCABAB"; String pattern = "ABABCABAB"; int index = bruteForceSearch(text, pattern); if (index != -1) { System.out.println("Pattern found at index " + index); } else { System.out.println("Pattern not found"); } }}
复制代码
评论