字串匹配：暴力搜尋算法 (Brute Force) 詳解

字串匹配：暴力搜尋算法 (Brute Force) 完整解析

算法特徵

• 無預處理階段
• 需常數額外空間
• 匹配失敗後模式串右移一位
• 字元比較順序任意
• 最壞時間複雜度 O(mn) (m=模式長, n=文本長)
• 文本字元期望比較次數 2n

算法描述

從文本位置 0 到 n-m 依次嘗試匹配。每次從模式串起始位置比較，若失敗則模式串右移一位繼續。無預處理，空間 O(1)。

C 語言實作

// 基礎版
int BF(char *x, int m, char *y, int n) {
    int i, j;
    for (j = 0; j <= n - m; ++j) {
        for (i = 0; i < m && x[i] == y[i + j]; ++i);
        if (i >= m) return j;  // 找到，返回起始位置
    }
    return -1;  // 未找到
}

// 優化版：利用 memcmp
#define EOS '\0'
int BF_opt(char *x, int m, char *y, int n) {
    char *yb = y;
    for (; *y != EOS; ++y)
        if (memcmp(x, y, m) == 0)
            return y - yb;
    return -1;
}

執行過程示例

文本：GCATCGCAGAGAGTATACAGTACG
模式：GCAGAGAG

共 17 次嘗試，第 6 次成功匹配（位置 5，0-based）。

複雜度分析

適用場景

• 模式串極短
• 文本較小、一次性搜尋
• 教學與基準比較
• 實際工程中通常優先考慮 KMP、Boyer-Moore、Sunday 等優化算法

1. 上一篇文章： Google C++ 風格指南核心規範摘要
2. 下一篇文章： Karp-Rabin 字符串匹配算法詳解

C++ 入門

UVA 11922 Permutation Transformer：Splay 树區間翻轉+分裂+合併

問題描述 初始排列 1..n。m 次操作 (a,b)：取出第

C++ 面向對象練習：矩形類與正方形判斷

實驗目的 設計一個矩形類 Zhengfx，實現輸入邊長、計算

ACM 題目 1474 DotA：技能遞減血量模擬

問題規則 英雄技能作用於目標血量 n： n 為偶數 → 砍

HDOJ 1348 Wall：凸包周長 + 圓周展開計算最短圍牆長度

問題轉化 城堡為多邊形，圍牆需距離城堡至少 L 單位。最短圍