Java在长字符串中查找短字符串的实现多种方法

下面我会详细讲解Java在长字符串中查找短字符串的实现多种方法。

目录

• 需求背景
• 传统字符串查找方式
• String类的indexOf方法
• Pattern类的matcher方法
• 优化的字符串查找方式
• Boyer-Moore算法
• KMP算法
• 总结

需求背景

在Java程序中处理长字符串时，经常需要进行短字符串的查找。例如，在字符串中查找单词、检查字符串中是否包含某段字符等等。传统的查找方式可能会带来性能上的问题，本文将介绍一些优化的字符串查找方式。

传统字符串查找方式

在介绍优化的字符串查找方式之前，先来看一下传统的字符串查找方式。

String类的indexOf方法

String类提供了indexOf方法来查找一个子串在目标字符串中第一次出现的位置。例如：

String str = "Hello, world!";
int index = str.indexOf("world");
System.out.println(index); // 输出：7

此处查找子串"world"在目标字符串中第一次出现的位置，返回结果为7。

但是，如果需要连续查找多个短字符串，每次调用indexOf方法都需要从头开始扫描目标字符串，这会降低查找效率。

Pattern类的matcher方法

Java提供了正则表达式来进行更为灵活的字符串匹配。Pattern类的matcher方法可以用来实现字符串的正则匹配。例如：

String str = "Hello, world!";
Pattern pattern = Pattern.compile("world");
Matcher matcher = pattern.matcher(str);
if (matcher.find()) {
    int index = matcher.start();
    System.out.println(index); // 输出：7
}

此处使用正则表达式"world"来查找目标字符串中第一次出现的位置。Matcher类中的find方法用于查找下一个匹配项，如果匹配到，则返回true，否则返回false。在查找到匹配项后，可以使用Matcher类的start方法获取匹配项在目标字符串中的起始位置。使用Pattern类和Matcher类进行字符串查找可以实现更为灵活的匹配操作，但是也会带来性能上的降低。

优化的字符串查找方式

针对传统字符串查找方式的性能问题，可以采用优化的字符串查找方式。本节将介绍两种常用的字符串查找算法：Boyer-Moore算法和KMP算法。

Boyer-Moore算法

Boyer-Moore算法是一种高效的字符串查找算法，其核心思想是利用匹配失败时的信息，将待匹配的字符串向右跳过尽可能多的字符，从而提高匹配效率。该算法主要包含两个步骤：

1. 预处理：根据目标字符串构建坏字符表和好后缀表。
2. 匹配：从文本串的右端开始匹配，不断跳过无用字符，直到找到匹配项或到达文本串的左端。

Boyer-Moore算法的预处理过程需要对目标字符串进行扫描，因此需要预处理的时间复杂度为O(m + k)，其中m为字符串长度，k为字符集大小。字符串的查找时间复杂度为O(n)，其中n为文本串长度。

下面是一个使用Boyer-Moore算法进行字符串查找的例子：

public static int boyerMooreStringMatch(String str, String pattern) {
    if (str == null || pattern == null) {
        return -1;
    }
    int n = str.length();
    int m = pattern.length();
    if (n < m) {
        return -1;
    }
    int[] badChar = getBadChar(pattern);
    int[] suffix = getGoodSuffix(pattern);
    int i = m - 1;
    int j = m - 1;
    while (i < n && j >= 0) {
        if (str.charAt(i) == pattern.charAt(j)) {
            i--;
            j--;
        } else {
            i = i + Math.max(j - badChar[str.charAt(i)], suffix[j + 1]);
            j = m - 1;
        }
    }
    if (j == -1) {
        return i + 1;
    } else {
        return -1;
    }
}

private static int[] getBadChar(String pattern) {
    int k = 256;
    int m = pattern.length();
    int[] badChar = new int[k];
    for (int i = 0; i < k; i++) {
        badChar[i] = m;
    }
    for (int i = 0; i < m - 1; i++) {
        badChar[pattern.charAt(i)] = m - 1 - i;
    }
    return badChar;
}

private static int[] getGoodSuffix(String pattern) {
    int m = pattern.length();
    int[] suffix = new int[m + 1];
    suffix[m] = m;
    int j = m;
    for (int i = m - 1; i >= 0; i--) {
        while (j <= m && pattern.charAt(i) != pattern.charAt(j - 1)) {
            if (suffix[j] == 0) {
                suffix[j] = j - i - 1;
            }
            j = suffix[j];
        }
        j--;
        suffix[i] = j;
    }
    return suffix;
}

KMP算法

KMP算法（Knuth-Morris-Pratt算法）是另一种高效的字符串查找算法，其核心思想是利用已经匹配过的信息，在匹配失败时尽量减少重复操作，从而提高匹配效率。该算法主要包括两个步骤：

1. 预处理：根据目标字符串构建next数组，记录每个位置在匹配失败时需要跳过的字符数。
2. 匹配：从文本串的左端开始匹配，不断跳过无用字符，直到找到匹配项或到达文本串的右端。

KMP算法的预处理过程需要对目标字符串进行扫描，因此需要预处理的时间复杂度为O(m)，其中m为字符串长度。字符串的查找时间复杂度为O(n)，其中n为文本串长度。

下面是一个使用KMP算法进行字符串查找的例子：

public static int kmpStringMatch(String str, String pattern) {
    if (str == null || pattern == null) {
        return -1;
    }
    int n = str.length();
    int m = pattern.length();
    if (n < m) {
        return -1;
    }
    int[] next = getNext(pattern);
    int i = 0;
    int j = 0;
    while (i < n && j < m) {
        if (j == -1 || str.charAt(i) == pattern.charAt(j)) {
            i++;
            j++;
        } else {
            j = next[j];
        }
    }
    if (j == m) {
        return i - m;
    } else {
        return -1;
    }
}

private static int[] getNext(String pattern) {
    int j = 0;
    int k = -1;
    int m = pattern.length();
    int[] next = new int[m + 1];
    next[0] = -1;
    while (j < m) {
        if (k == -1 || pattern.charAt(j) == pattern.charAt(k)) {
            j++;
            k++;
            next[j] = k;
        } else {
            k = next[k];
        }
    }
    return next;
}

总结

本文介绍了Java中在长字符串中查找短字符串的实现多种方法，包括传统的字符串查找方式和优化的字符串查找方式。传统的字符串查找方式包括String类的indexOf方法和Pattern类的matcher方法，优化的字符串查找方式包括Boyer-Moore算法和KMP算法。在实际应用中，可以根据具体需求选择合适的字符串查找方式。