HDU 1711 Number Sequence：KMP 算法求子串首次出現位置

問題描述

給定長度 N≤1e6 的主串 A 和長度 M≤1e4 的模式串 B，找 B 在 A 中首次出現的起始位置 (1-based)。多測試用例。

核心算法：KMP (Knuth-Morris-Pratt)

預處理模式串 B 計算 next 數組（最長公共前後綴長度），匹配時利用 next 跳過無效比較，達到 O(N+M)。

next 數組構建 (1-based 索引)

// B[1..M]
next[1] = 0;
for (int i=2, j=0; i<=M; ++i) {
    while (j > 0 && B[i] != B[j+1]) j = next[j];
    if (B[i] == B[j+1]) ++j;
    next[i] = j;
}

匹配過程

int j = 0;
for (int i=1; i<=N; ++i) {
    while (j > 0 && (j == M || A[i] != B[j+1])) j = next[j];
    if (A[i] == B[j+1]) ++j;
    if (j == M) {
        pos = i - M + 1; // 找到
        break;
    }
}

完整代碼 (C++)

const int MAXN = 1000000 + 10;
const int MAXM = 10000 + 10;
int A[MAXN], B[MAXM], next[MAXM];

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        int N, M; scanf("%d%d", &N, &M);
        for (int i=1; i<=N; ++i) scanf("%d", &A[i]);
        for (int i=1; i<=M; ++i) scanf("%d", &B[i]);

        // 建 next
        next[1] = 0;
        for (int i=2, j=0; i<=M; ++i) {
            while (j && B[i] != B[j+1]) j = next[j];
            if (B[i] == B[j+1]) ++j;
            next[i] = j;
        }

        // KMP 匹配
        int ans = -1;
        for (int i=1, j=0; i<=N; ++i) {
            while (j && (j==M || A[i] != B[j+1])) j = next[j];
            if (A[i] == B[j+1]) ++j;
            if (j == M) { ans = i - M + 1; break; }
        }
        printf("%d\n", ans);
    }
    return 0;
}

複雜度分析

• 時間：O(N+M) 每測試用例，總數據量大但線性算法極快。
• 空間：O(N+M) 存儲數組。

關鍵點

• 整數數組匹配：非字符串，直接比較 int 值。
• 1-based 索引：代碼簡潔，next[i] 表示 B[1..i] 的最長公共前後綴長度。
• 多測試用例：每案例重新讀入、計算 next、匹配。

總結

HDU 1711 是 KMP 算法在整數序列上的標準應用。掌握 next 數組構建與匹配跳轉邏輯，是字符串/序列匹配問題的核心基本功。