子串出現次數統計：暴力匹配算法在主串中查找子串頻率

問題描述

輸入主串 str 和子串 s（長度均 ≤ 128），統計 s 在 str 中出現的次數（可重疊）。

暴力匹配算法

對主串每個位置 i，嘗試匹配子串：

1. 若 str[i] == s[0]，從 i 開始逐字符比較
2. 若全部匹配成功，計數器++
3. 繼續檢查下一位置（允許重疊）

代碼實現

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

int main() {
    int i, j, l, n, m, count, flag;
    char a[129], b[129];

    gets(a);
    gets(b);
    n = strlen(a);
    m = strlen(b);
    count = 0;

    for (i = 0; i < n; i++) {
        flag = 1;
        if (a[i] == b[0]) {
            l = i;
            for (j = 1; j < m; j++) {
                if (b[j] != a[++l]) {
                    flag = 0;
                    break;
                }
            }
            if (flag) count++;
        }
    }

    printf("%d", count);
    return 0;
}

進階：KMP 算法

若字符串極長，可用 KMP 算法 O(n+m) 替代暴力 O(n×m)。構建 next 數組，失配時快速跳過已知匹配前綴。

測試樣例

輸入：

sdf$$$sdf$$
sdf

輸出： 2

主串中 "sdf" 出現在位置 0 和 6，共 2 次。