HDU 1711 Number Sequence：KMP 整數數組匹配

題目大意

給定兩個整數序列 a (長度 N ≤ 1,000,000) 和 b (長度 M ≤ 10,000)。找最小的 K 使得 a[K..K+M-1] = b[1..M]。不存在輸出 -1。多組測試。

核心思路

標準 KMP 算法直接適用於整數數組，只需將字符比較改為整數比較。next 數組構建和匹配邏輯完全相同。

演算法步驟

1. 讀入 N, M 和兩個序列
2. 對模式串 b 計算 next 數組
3. 在文本串 a 上進行 KMP 匹配
4. 匹配成功返回位置 (1-based)，失敗返回 -1

關鍵點

• 數據範圍大，使用靜態數組避免 vector 開銷
• 整數範圍 [-1000000, 1000000]，直接比較無需離散化
• next 數組 0-indexed 實現，匹配時返回 i-j+1 (1-based)

完整代碼

#include <iostream>
#include <cstdio>
using namespace std;

#define N 1000005
int n, m;
int a[N], b[N];
int nxt[N];

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

int kmp(int *text, int *pat) {
    int i = 0, j = 0;
    while (i < n) {
        if (j == -1 || text[i] == pat[j]) { i++; j++; }
        else j = nxt[j];
        if (j == m) return i - j + 1; // 1-based
    }
    return -1;
}

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        scanf("%d%d", &n, &m);
        for (int i = 0; i < n; i++) scanf("%d", &a[i]);
        for (int i = 0; i < m; i++) scanf("%d", &b[i]);
        getFail(b);
        printf("%d\n", kmp(a, b));
    }
    return 0;
}

複雜度分析

預處理 O(M)，匹配 O(N)，總時間 O(N+M)，空間 O(N+M)。完美應對百萬級數據。