Java 統計子字符串在父字符串中出現次數：高效算法實現

問題描述

給定父字符串 strFather 和子字符串 strSub，統計 strSub 在 strFather 中不重疊出現的次數。例如：「ababab」中「ab」出現 3 次，「aaa」中「aa」出現 1 次 (不重疊)。

核心算法：滑動窗口 + 索引跳躍

public class SubstringCounter {
    
    /**
     * 統計子串非重疊出現次數
     * @param father 父字符串
     * @param sub 子字符串
     * @return 出現次數
     */
    public static int countOccurrences(String father, String sub) {
        if (father == null || sub == null || sub.isEmpty()) {
            return 0;
        }
        
        int count = 0;
        int subLen = sub.length();
        int fatherLen = father.length();
        int i = 0;
        
        // 只需遍歷到 fatherLen - subLen，之後剩餘長度不足匹配
        while (i <= fatherLen - subLen) {
            // 提取當前窗口子串
            String window = father.substring(i, i + subLen);
            
            if (sub.equals(window)) {
                count++;
                i += subLen; // 命中：索引跳過整個子串長度 (不重疊)
            } else {
                i++; // 未命中：索引後移一位
            }
        }
        return count;
    }

    // 測試
    public static void main(String[] args) {
        String str = "abeefddfadeeabfkkeeabeeabeerfab";
        System.out.println("子串 'ab' 出現次數: " + countOccurrences(str, "ab")); // 4
        System.out.println("子串 'ee' 出現次數: " + countOccurrences(str, "ee")); // 4
        System.out.println("子串 'f' 出現次數: " + countOccurrences(str, "f"));   // 6
        
        // 邊界測試
        System.out.println("'aaa' 中 'aa': " + countOccurrences("aaa", "aa")); // 1 (不重疊)
        System.out.println("'aaaa' 中 'aa': " + countOccurrences("aaaa", "aa")); // 2
        System.out.println("空子串: " + countOccurrences("abc", "")); // 0
        System.out.println("null 父串: " + countOccurrences(null, "a")); // 0
    }
}

算法複雜度分析

進階優化方案

1. 避免 substring 創建對象：使用 regionMatches

// 替換 substring + equals
if (father.regionMatches(i, sub, 0, subLen)) {
    count++;
    i += subLen;
} else {
    i++;
}

regionMatches 直接比較字符數組區間，無新對象分配，性能顯著提升。

2. KMP / Boyer-Moore 算法 (O(n+m))

對於超長文本 (GB 級) 或高頻調用，建議使用標準庫或成熟庫：

// Apache Commons Lang
int count = StringUtils.countMatches(father, sub); 

// 或 Java 9+ Stream (但會統計重疊)
long count = father.chars()... // 不推薦用於非重疊統計

3. 正則表達式 (需轉義特殊字符)

import java.util.regex.*;
public static int countByRegex(String father, String sub) {
    String pattern = Pattern.quote(sub); // 自動轉義 . * ? 等元字符
    Matcher matcher = Pattern.compile(pattern).matcher(father);
    int count = 0;
    while (matcher.find()) count++;
    return count;
}

正則預編譯後匹配速度極快，且天然支持不重疊語義。

常見陷阱與測試用例

總結建議

1. 一般業務：使用 regionMatches 版本，無依賴、高性能、語義清晰。
2. 高性能場景：引入 Apache Commons Lang 的 StringUtils.countMatches。
3. 複雜匹配：需正則功能時用 Pattern.quote + Matcher.find()。
4. 切記：明確業務是否允許重疊，本文實現為不重疊統計。