C語言練習實例96：統計子串在母串中出現的次數

本實例演示如何計算一個子串在母串中出現的次數（允許重疊）。

程序分析

採用暴力匹配算法：

1. 讀取母串 T 和子串 P。
2. 外層循環遍歷母串每個可能的起始位置 i（從 0 到 TLen - PLen）。
3. 內層循環比對子串各字符，若全部匹配則計數器 count 加一。
4. 最後輸出計數結果。

源代碼

// Created by www.runoob.com on 15/11/9.
// Copyright © 2015年 菜鳥教程. All rights reserved.
//
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main() {
    int i, j, k, TLen, PLen, count = 0;
    char T[50], P[10];

    printf("請輸入兩個字符串，以回車隔開，母串在前，子串在後：\n");
    gets(T);
    gets(P);

    TLen = strlen(T);
    PLen = strlen(P);

    for (i = 0; i <= TLen - PLen; i++) {
        for (j = 0, k = i; j < PLen && P[j] == T[k]; j++, k++)
            ; // 空循環體
        if (j == PLen)
            count++;
    }

    printf("%d\n", count);
    system("pause");
    return 0;
}

運行示例

請輸入兩個字符串，以回車隔開，母串在前，子串在後：
abca
a
2

母串 abca 中子串 a 出現 2 次。

註記

• 此算法時間複雜度為 O(n*m)，適合短字符串；長文本建議使用 KMP 等高效算法。
• 同樣存在 gets() 安全隱患。