HDU 2087 剪花布條：KMP 算法求最大不重疊子串出現次數

題目大意

給定「花布條」主串 S 與「小飾條」模式串 T（均由可見 ASCII 字元組成，長度 ≤ 1000），求從 S 中最多能剪出多少個不重疊的 T。輸入以 # 結束。

核心約束：不重疊

標準 KMP 找到匹配後通常將主串指針回退以尋找下一個可能匹配（允許重疊）。本題要求不重疊，策略為：匹配成功後，主串指針直接跳過整個模式串長度，模式串指針重置為 0。

KMP 核心邏輯

1. 構建 next[] 數組（部分匹配表）：next[j] 表示模式串 0..j-1 的最長真前綴等於真後綴的長度。失配時 j = next[j]，避免主串回退。
2. 匹配過程：
   • i 遍歷主串，j 遍歷模式串
   • 匹配則 i++, j++
   • 失配則 j = next[j]；若 j == -1 則 i++, j = 0
   • 關鍵修改：當 j == m（完整匹配）時，ans++，j = 0（而非 next[j]），實現不重疊。

完整 C++ 實現

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1000005;
char S[MAXN], T[MAXN];
int nxt[MAXN];

void build_next(const char *pat) {
    int m = strlen(pat);
    nxt[0] = -1;
    int i = 0, j = -1;
    while (i < m) {
        if (j == -1 || pat[i] == pat[j]) {
            nxt[++i] = ++j;
        } else {
            j = nxt[j];
        }
    }
}

int kmp_count(const char *text, const char *pat) {
    int n = strlen(text), m = strlen(pat);
    if (m == 0) return 0;
    build_next(pat);
    int i = 0, j = 0, ans = 0;
    while (i < n) {
        if (j == -1 || text[i] == pat[j]) {
            i++; j++;
        } else {
            j = nxt[j];
        }
        if (j == m) {      // 找到一次完整匹配
            ans++;
            j = 0;         // ★ 不重疊：模式串指針歸零，主串指針 i 不回退
        }
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    while (cin >> S) {
        if (S[0] == '#') break;
        cin >> T;
        cout << kmp_count(S, T) << '\n';
    }
    return 0;
}

範例驗證

輸入：
abcde a3
aaaaaa aa
#

輸出：
0
3

解析：aaaaaa 中 aa 不重疊最多出現 3 次（位置 0-1, 2-3, 4-5）。

複雜度與優勢

• 時間：O(N + M) — 線性掃描，主串指針永不回退
• 空間：O(M) — next 數組
• 適用於長文本、多測試用例場景

常見錯誤提醒

• ❌ 匹配後用 j = nxt[j] → 允許重疊（如 aaaa 匹配 aa 得 3 次而非 2）
• ❌ 忘記處理 j == -1 的邊界條件
• ❌ 輸入包含空格時用 cin >> S 會截斷 → 本題「可見 ASCII」無空格，安全