字符串子串計數算法：順序遍歷 + strncmp 實現

問題描述

給定主字符串 `str` 和子字符串 `sub_str`，統計 `sub_str` 在 `str` 中出現的次數（允許重疊）。若無出現返回 0。

示例：`str="asderwsde"`, `sub_str="sde"` → 出現 2 次（位置 2 和 6）。

算法思路

1. 計算長度：`len_str = strlen(str)`, `len_sub = strlen(sub_str)`。
2. 若 `len_sub > len_str` 直接返回 0。
3. 滑動窗口遍歷：從 `str[0]` 到 `str[len_str - len_sub]`，每次用 `strncmp(str+i, sub_str, len_sub)` 比較前 `len_sub` 字符。
4. 相等則計數器++。

時間複雜度

O((N-M+1) * M)，N 為主串長，M 為子串長。對於小規模數據足夠；大規模建議 KMP (O(N+M)) 或 Boyer-Moore。

C 語言實現

#include <stdio.h>
#include <string.h>

int sub_str_count(const char *str, const char *sub_str) {
    int str_len = strlen(str);
    int sub_len = strlen(sub_str);
    if (sub_len == 0 || sub_len > str_len) return 0;

    int count = 0;
    int limit = str_len - sub_len + 1;
    for (int i = 0; i < limit; ++i) {
        if (strncmp(str + i, sub_str, sub_len) == 0)
            ++count;
    }
    return count;
}

int main(int argc, char *argv[]) {
    if (argc != 3) {
        fprintf(stderr, "Usage: %s  \n", argv[0]);
        return 1;
    }
    printf("%s ---- %s ---> %d\n", argv[1], argv[2], sub_str_count(argv[1], argv[2]));
    return 0;
}

編譯與測試

$ gcc substr_count.c -o substr_count
$ ./substr_count "asderwsde" "sde"
asderwsde ---- sde ---> 2
$ ./substr_count "aaaaa" "aa"
aaaaa ---- aa ---> 4  (重疊計數: 0,1,2,3)

進階優化方向

• KMP 算法：預處理 `next` 數組，避免回溯主串指針，O(N+M)。
• Sunday / Boyer-Moore：利用坏字符规则跳過更多比較，實際性能更優。
• 標準庫：C++ 可用 `std::string::find` 循環，或 Boost `find_all`。

總結

順序遍歷配合 `strncmp` 是最直觀、代碼最簡潔的子串計數方法，適合教學、面試及小數據場景。理解其局限性並知道何時升級到 KMP 等高級算法，是工程師的基本功。