C語言數據結構：字符串 BF 算法（暴力匹配）完整實現

編輯：關於C語言

C語言數據結構：字符串 BF 算法（暴力匹配）完整實現

BF 算法（Brute-Force）是最直觀的字符串模式匹配算法。本文實現一個完整的動態字符串結構體（DString），包含初始化、插入、刪除、子串提取、銷毀等操作，並在此基礎上實現 BF 匹配。

一、動態字符串結構體設計

typedef struct {
    char *str;        // 字符數據指針
    int maxLength;    // 分配的最大容量
    int length;       // 當前有效長度
} DString;

二、核心操作函數

1. 初始化

void Initiate(DString *s, int max, char *string) {
    s->str = (char*)malloc(sizeof(char) * max);
    s->maxLength = max;
    s->length = strlen(string);
    for (int i = 0; i < s->length; i++) s->str[i] = string[i];
}

2. 插入子串


int Insert(DString *s, int pos, DString t) {
    if (pos < 0) return 0;
    // 擴容檢查
    if (s->length + t.length > s->maxLength) {
        s->str = 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;
}

3. 刪除子串


int Delete(DString *s, int pos, int len) {
    if (s->length <= 0 || pos < 0 || len < 0 || pos + len > s->length) return 0;
    for (int i = pos + len; i <= s->length - 1; i++)
        s->str[i - len] = s->str[i];  // 前移覆蓋
    s->length -= len;
    return 1;
}

4. 取子串


int SubString(DString *s, int pos, int len, DString *t) {
    if (pos < 0 || len < 0 || pos + len > s->length) return 0;
    if (len > t->maxLength) {
        t->str = realloc(t->str, len * sizeof(char));
        t->maxLength = len;
    }
    for (int i = 0; i < len; i++) t->str[i] = s->str[pos + i];
    t->length = len;
    return 1;
}

5. 銷毀


void Destroy(DString *s) {
    free(s->str);
    s->maxLength = s->length = 0;
}

三、BF 匹配算法核心


// 返回子串 t 在主串 s 中從 start 位置開始的首次匹配下標，失敗返回 -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 s1, s2;
    Initiate(&s1, 29, "Data Structure Data Structure");
    Initiate(&s2, 9, "Structure");

    int pos = 0;
    pos = BFIndex(s1, pos, s2);
    printf("第一次匹配位置: %d\n", pos);  // 5

    pos = BFIndex(s1, pos + 1, s2);
    printf("第二次匹配位置: %d\n", pos); // 22

    Destroy(&s1); Destroy(&s2);
    return 0;
}

五、算法複雜度與優缺點

指標	數值
時間複雜度	O(n*m) 最壞情況（n=主串長，m=模式串長）
空間複雜度	O(1) 額外空間
優點	實現簡單，無需預處理，小數據/短模式串效果好
缺點	大量部分匹配後失敗時回退導致效率低