在字符串中搜索多个子串的最快方法，现有Java实现是否高效？

架构老林

2026-10-5

你提供的用于统计子串出现次数的Java代码如下：

public static void main(String... args) {
    String fullString = "one is a good one. two is ok. three is three. four is four. five is not four";
    String[] severalStringArray = { "one", "two", "three", "four" };
    Map<String, Integer> countMap = countWords(fullString, severalStringArray);
}

public static Map<String, Integer> countWords(String fullString, String[] severalStringArray) {
    Map<String, Integer> countMap = new HashMap<>();

    for (String searchString : severalStringArray) {
        if (countMap.containsKey(searchString)) {
            int searchCount = countMatchesInString(fullString, searchString);
            countMap.put(searchString, countMap.get(searchString) + searchCount);
        } else
            countMap.put(searchString, countMatchesInString(fullString, searchString));
    }

    return countMap;
}

private static int countMatchesInString(String fullString, String subString) {
    int count = 0;
    int pos = fullString.indexOf(subString);
    while (pos > -1) {
        count++;
        pos = fullString.indexOf(subString, pos + 1);
    }
    return count;
}

原实现效率评估

这个实现不算高效，尤其当你要处理的是大文件级别的主串、待搜索子串数量较多的时候，性能会下降得很明显。核心问题是逻辑为每新增一个要搜索的子串，就得完整扫描一遍整个主串，时间复杂度是O(k*N)，k是待搜子串的数量，N是主串长度，子串越多，重复遍历的开销就越大。
另外代码里还有冗余逻辑：countWords方法里的countMap.containsKey判断作用很小，只有你传入的待搜索子串数组里有重复元素的时候才会触发累加，要是数组本身已经去重了，这段判断完全多余。

更优实现方案

根据使用场景可以选不同的优化方案：

如果是要匹配任意子串、待搜索的子串数量比较多：优先用AC自动机（Aho-Corasick）多模式匹配算法，只需要扫描一遍主串就能统计出所有子串的出现次数，时间复杂度直接降到O(N + 所有待搜索子串的总长度)，不管有多少个待匹配子串都不用重复扫描主串，是这类场景的最优解。
如果你的需求是统计完整单词的出现次数，不需要把嵌在其他单词里的子串算成匹配结果：可以先把主串按分隔符（比如非字母、数字、符号）拆成一个个独立单词，再遍历单词列表用哈希表匹配待搜索的词统计次数，性能比子串匹配高很多。
如果待搜索的子串只有2、3个，数量极少：没必要引入复杂的多模式匹配算法，先把待搜索数组去重之后用原来的逻辑就行，Java内置的indexOf已经做了底层优化，少量子串的场景下性能够用。
如果处理的是特别大的文件：不用一次性把整个文件读进内存转成字符串，可以边读文件流边做匹配，配合AC自动机还能大幅降低内存占用，避免大文件加载导致的内存溢出。

内容的提问来源于stack exchange，提问作者integ specialist