C 語言字符串匹配算法詳解：統計子串在主串中出現次數的雙重循環實現

問題描述

實現 int fun(char *s1, char *s2)，統計 s2 在 s1 中出現次數，不重疊計數。

標準代碼

int fun(char *s1, char *s2) {
    int i, j, len1 = strlen(s1), len2 = strlen(s2), n = 0;
    for (i = 0; i <= len1 - len2; i++) {          // 外層：滑動窗口起始位置
        for (j = 0; j < len2; j++) {              // 內層：逐字符比較
            if (*(s1 + i + j) != *(s2 + j)) break; // 指針算術訪問
        }
        if (j == len2) {                          // 完全匹配
            i += j - 1;                           // 跳過已匹配部分（關鍵優化）
            n++;
        }
    }
    return n;
}

逐行註釋

測試用例

s1 = "abaaAabcaabbabca", s2 = "ab"  → n = 4
s1 = "abaaAabcaabbabca", s2 = "abd" → n = 0 (輸出 "No find")

複雜度

• 時間 O((n-m+1)×m) 最壞 O(nm)，n=主串長，m=子串長。
• 空間 O(1)。

優化方向

大數據量建議 KMP、Boyer-Moore 或 Sunday 算法，將時間降至 O(n+m)。