您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C >> 關於C

C 語言資料結構：動態字串結構與暴力模式匹配 (BF 算法) 實作

編輯：關於C

動態字串結構 `DString`

為支援任意長度字串並提供基本編輯操作，定義結構體：


typedef struct {
    char *str;        // 字元資料區
    int   maxLength;  // 配置容量上限
    int   length;     // 目前有效長度 (不含 \0)
} DString;

核心操作函數

函數	功能	回傳
`Initiate(s, max, initStr)`	初始化並複製初始字串	void
`Insert(s, pos, t)`	在 `pos` 插入子串 `t`，空間不足自動 `realloc`	1 成功 / 0 失敗
`Delete(s, pos, len)`	刪除 `pos` 起長度 `len` 的子串	1/0
`SubString(s, pos, len, t)`	提取子串至 `t`，空間不足自動擴充	1/0
`Destroy(s)`	釋放記憶體，歸零欄位	void

插入實作精華


int Insert(DString *s, int pos, DString t) {
    if (pos < 0) return 0;
    if (s->length + t.length > s->maxLength) {
        s->str = (char *)realloc(s->str, (s->length + t.length) * sizeof(char));
        s->maxLength = s->length + t.length;
    }
    // 從尾部向前搬移騰出空間
    for (int i = s->length - 1; i >= pos; --i)
        s->str[i + t.length] = s->str[i];
    // 複製新資料
    for (int i = 0; i < t.length; ++i)
        s->str[pos + i] = t.str[i];
    s->length += t.length;
    return 1;
}

暴力模式匹配 (Brute-Force, BF) 算法

又稱朴素匹配，核心邏輯：

i 掃描主串 s，j 掃描模式串 t。
字元匹配則 i++、j++；失配則 i = i - j + 1、j = 0（主串回溯至下一起始位置）。
若 j == t.length 表示完全匹配，回傳起始索引 i - t.length；掃描結束未匹配回傳 -1。


int BFIndex(DString s, int start, DString t) {
    int i = start, j = 0;
    while (i < s.length && j < t.length) {
        if (s.str[i] == t.str[j]) { ++i; ++j; }
        else { i = i - j + 1; j = 0; }
    }
    return (j == t.length) ? (i - t.length) : -1;
}

測試主程式


int main() {
    DString text, pattern;
    Initiate(&text, 29, "Data Structure Data Structure");
    Initiate(&pattern, 9, "Structure");
    
    int pos = 0;
    pos = BFIndex(text, pos, pattern);
    printf("第一次匹配位置: %d\n", pos);  // 輸出 5
    
    pos = BFIndex(text, pos + 1, pattern);
    printf("第二次匹配位置: %d\n", pos);  // 輸出 19
    
    Destroy(&text);
    Destroy(&pattern);
    return 0;
}

複雜度分析與優化方向

指標	BF 算法	備註
時間複雜度	O(n·m)	最壞情況：主串 `aaa...ab`，模式串 `aaab`，大量回溯
空間複雜度	O(1)	僅常數額外空間
適用場景	短模式、低重複字元、教學驗證	長文本/高重複建議 KMP、BM、Sunday 等