NYOJ Binary String Matching - BF 算法模式匹配

題目大意

給定模式串 A (長度 ≤ 10) 和文本串 B (長度 ≤ 1000)，僅含 '0'/'1'。求 A 在 B 中作為子串出現的次數 (可重疊)。多測資。

BF (Brute Force) 算法

雙指針 i (文本), j (模式)。匹配則 i++, j++；失配則 i = i - j + 1, j = 0 (回退到文本下一位置重新匹配)。
j == lenA 時計數++，i = i - lenA + 1 允許重疊匹配 (如 AAA 中找 AA 得 2 次)。

完整代碼

#include 
using namespace std;

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        char A[15], B[1005];
        scanf("%s %s", A, B);
        int lenA = strlen(A), lenB = strlen(B);
        int cnt = 0;
        for (int i = 0; i <= lenB - lenA; ++i) {
            bool match = true;
            for (int j = 0; j < lenA; ++j)
                if (B[i+j] != A[j]) { match = false; break; }
            if (match) ++cnt;
        }
        printf("%d\n", cnt);
    }
    return 0;
}

上述為簡化版雙層迴圈 (同 BF 邏輯)。原文給出標準指針回退版，效果相同。

複雜度

• 時間：O(lenA × lenB) ≤ 10 × 1000 = 10000 每測資，T 組總計極快。
• 空間：O(1)。

延伸：KMP 優化

若模式串長 (如 10⁵)，需 KMP O(lenA + lenB)。本題模式極短 (≤10)，BF 完全足夠，代碼更簡短不易出錯。