HDU 1711：數列匹配——KMP 算法入門經典

問題描述

給定文本串 a[1..N] (N ≤ 10⁶) 和模式串 b[1..M] (M ≤ 10⁴)，找到模式串在文本串中首次出現的起始位置 K（1-based）。若不存在輸出 -1。多組測試數據。

KMP 核心思想

利用模式串的「最長公共前後綴」信息（next 數組），在匹配失敗時避免文本串指針回溯，實現 O(N+M) 線性匹配。

next 數組構建

next[i] 表示模式串前 i 個字符（0-indexed 下標 0..i-1）的最長真前綴同時也是後綴的長度。構建過程：

void buildNext() {
    next[0] = -1;
    int j = -1;
    for (int i = 1; i < m; i++) {
        while (j >= 0 && pattern[j+1] != pattern[i]) j = next[j];
        if (pattern[j+1] == pattern[i]) j++;
        next[i] = j;
    }
}

匹配過程

int kmp() {
    int j = -1;
    for (int i = 0; i < n; i++) {
        while (j >= 0 && pattern[j+1] != text[i]) j = next[j];
        if (pattern[j+1] == text[i]) j++;
        if (j == m-1) return i - m + 2; // 1-based 位置
    }
    return -1;
}

完整代碼

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

int text[1000007], pattern[10007];
int next[10007], n, m;

void buildNext() {
    next[0] = -1;
    int j = -1;
    for (int i = 1; i < m; i++) {
        while (j >= 0 && pattern[j+1] != pattern[i]) j = next[j];
        if (pattern[j+1] == pattern[i]) j++;
        next[i] = j;
    }
}

int kmp() {
    int j = -1;
    for (int i = 0; i < n; i++) {
        while (j >= 0 && pattern[j+1] != text[i]) j = next[j];
        if (pattern[j+1] == text[i]) j++;
        if (j == m-1) return i - m + 2;
    }
    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", &text[i]);
        for (int i = 0; i < m; i++) scanf("%d", &pattern[i]);
        buildNext();
        printf("%d\n", kmp());
    }
    return 0;
}

關鍵點總結

• 整數數列匹配，直接用整數比較，無需字符串處理。
• next 數組下標含義統一：next[i] 對應前 i+1 個字符的最長公共前後綴長度。
• 匹配時文本指針 i 只增不減，模式指針 j 根據 next 回退，保證 O(N+M)。
• 返回位置為 1-based：i - m + 2（i 為 0-based 終點索引）。
• 數組大小開足：text[1000007], pattern[10007], next[10007]。

變體提示

若需求所有出現位置，匹配成功後 j = next[j] 繼續；若模式串含重複前綴，next 正確構建至關重要。