如何用Java实现字符串匹配和替换的高效算法？

Java中有多种方法可以实现字符串匹配和替换的高效算法。下面将介绍一些常见的算法和实现方式，并提供一些示例代码。

1、字符串匹配算法：

1.1. Brute Force（暴力法）：

这是最简单的字符串匹配算法，也是最低效的。它的思想是逐个比较目标字符串中的字符与要匹配的子字符串字符是否相等。时间复杂度为O(mn)，其中m是目标字符串长度，n是子字符串长度。

public static int bruteForceSearch(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) {
            return i;
        }
    }
    
    return -1;
}

1.2. KMP算法：

KMP（Knuth-Morris-Pratt）算法通过利用已经匹配过的信息来减少不必要的字符比较次数，进而提高效率。时间复杂度为O(m+n)。

public static int kmpSearch(String text, String pattern) {
    int n = text.length();
    int m = pattern.length();
    int[] lps = computeLPSArray(pattern);
    
    int i = 0;
    int j = 0;
    while (i < n) {
        if (pattern.charAt(j) == text.charAt(i)) {
            i++;
            j++;
        }
        
        if (j == m) {
            return i - j;
        } else if (i < n && pattern.charAt(j) != text.charAt(i)) {
            if (j != 0) {
                j = lps[j - 1];
            } else {
                i++;
            }
        }
    }
    
    return -1;
}

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;
}

1.3. Boyer-Moore算法： Boyer-Moore算法通过预处理模式串，跳过尽可能多的字符，从而实现快速的字符串匹配。时间复杂度为O(mn)。

public static int boyerMooreSearch(String text, String pattern) {
    int n = text.length();
    int m = pattern.length();
    int[] badChar = buildBadCharTable(pattern);
    int[] goodSuffix = buildGoodSuffixTable(pattern);
    
    int i = 0;
    while (i <= n - m) {
        int j = m - 1;
        while (j >= 0 && pattern.charAt(j) == text.charAt(i + j)) {
            j--;
        }
        
        if (j < 0) {
            return i;
        } else {
            int shift1 = j - badChar[text.charAt(i + j)];
            int shift2 = 0;
            if (j < m - 1) {
                shift2 = moveByGoodSuffix(j, m, goodSuffix);
            }
            
            i += Math.max(shift1, shift2);
        }
    }
    
    return -1;
}

private static int[] buildBadCharTable(String pattern) {
    int m = pattern.length();
    int[] table = new int[256];
    Arrays.fill(table, -1);
    
    for (int i = 0; i < m; i++) {
        table[pattern.charAt(i)] = i;
    }
    
    return table;
}

private static int[] buildGoodSuffixTable(String pattern) {
    int m = pattern.length();
    int[] suffix = new int[m];
    int[] prefix = new int[m];
    int lastPrefixPosition = m;
    
    for (int i = m - 1; i >= 0; i--) {
        if (isPrefix(pattern, i + 1)) {
            lastPrefixPosition = i + 1;
        }
        prefix[i] = lastPrefixPosition - i + m - 1;
    }
    
    for (int i = 0; i < m; i++) {
        int suffixLen = 0;
        if (i > 0) {
            suffixLen = computeSuffixLen(pattern, i, prefix);
        }
        suffix[suffixLen] = i;
    }
    
    return suffix;
}

private static boolean isPrefix(String pattern, int p) {
    int m = pattern.length();
    for (int i = p, j = 0; i < m; i++, j++) {
        if (pattern.charAt(i) != pattern.charAt(j)) {
            return false;
        }
    }
    return true;
}

private static int computeSuffixLen(String pattern, int p, int[] prefix) {
    int m = pattern.length();
    int len = 0;
    int j = m - 1;
    for (int i = p; i >= 0 && pattern.charAt(i) == pattern.charAt(j); i--, j--) {
        len += prefix[j];
    }
    return len;
}

private static int moveByGoodSuffix(int j, int m, int[] goodSuffix) {
    int k = m - 1 - j;
    if (goodSuffix[k] != -1) {
        return j - goodSuffix[k] + 1;
    }
    
    for (int r = j + 2; r <= m - 1; r++) {
        if (goodSuffix[m - r] != -1) {
            return r - goodSuffix[m - r];
        }
    }
    
    return m;
}

2、字符串替换算法： Java中提供了String类的replace()方法用于进行简单的字符串替换。如果需要进行复杂的模式匹配和替换，可以使用正则表达式。

2.1. 使用String类的replace()方法：

String str = "Hello, World!";
String replacedStr = str.replace("World", "Java");

在上面的示例中，我们将字符串"Hello, World!"中的"World"替换为"Java"。

2.2. 使用正则表达式进行替换：

String str = "The quick brown fox jumps over the lazy dog.";
String replacedStr = str.replaceAll("fox|dog", "cat");

在上面的示例中，我们使用replaceAll()方法通过正则表达式将字符串中的"fox"和"dog"替换为"cat"。

无论是字符串匹配还是替换，选择合适的算法和方法取决于具体的需求。在实际应用中，可以根据字符串的长度和匹配/替换的频率来评估不同算法的性能，从而选择最合适的算法。

原文始发于微信公众号（学习编程技术）：如何用Java实现字符串匹配和替换的高效算法？