HDU 1711 Number Sequence：整數序列上的 KMP 算法詳解

HDU 1711 Number Sequence：整數序列上的 KMP 算法詳解

本題要求在一個長度為 N 的整數序列中，尋找長度為 M 的模式序列首次出現的位置。這是經典 KMP（Knuth-Morris-Pratt）算法在整數數組上的直接應用，核心邏輯與字符串匹配完全一致，只需將字符比較改為整數比較。

核心思路

KMP 算法通過預處理模式序列構建 next 數組（也稱失敗函數），記錄每個位置之前最長的「前綴等於後綴」的長度。匹配時，一旦發生失配，可根據 next 數組快速跳過已知匹配的部分，避免主序列指針回溯，實現 O(N+M) 的線性時間複雜度。

關鍵代碼實現

#include <stdio.h>
#include <string.h>

const int MAX_N = 1000001;
const int MAX_M = 10001;

int strN[MAX_N], strM[MAX_M], next[MAX_M];
int N, M;

// 構建 next 數組
void getNext() {
    memset(next, 0, sizeof(int) * M);
    for (int i = 1, j = 0; i < M; ) {
        if (strM[i] == strM[j]) {
            next[i++] = ++j;
        } else if (j > 0) {
            j = next[j-1];
        } else {
            i++;
        }
    }
}

// KMP 搜索
int kmpSearch() {
    int i = 0, j = 0;
    for ( ; M - j <= N - i && j < M; ) {
        if (strN[i] == strM[j]) {
            i++; j++;
        } else if (j > 0) {
            j = next[j-1];
        } else {
            i++;
        }
    }
    if (j == M) return i - M + 1; // 題目要求位置從 1 開始
    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", strN + i);
        for (int i = 0; i < M; i++) scanf("%d", strM + i);
        getNext();
        printf("%d\n", kmpSearch());
    }
    return 0;
}

注意事項

• 數組大小需根據題目約束開啟足夠空間（MAX_N=1e6+1, MAX_M=1e4+1）。
• next 數組構建時索引從 1 開始，next[0] 默認為 0。
• 匹配時邊界條件 M-j <= N-i 可提前終止無法匹配的情況。
• 返回位置需 +1 以符合題目「從 1 開始計數」的要求。

此題是 KMP 算法從字符串擴展到整數序列的典型範例，掌握其核心遞推邏輯對解決各類模式匹配問題至關重要。