KMP 字符串匹配算法：從原理到改進版完整 C 實現

編輯：關於C語言

算法背景

KMP（Knuth-Morris-Pratt）算法是經典的線性時間字符串匹配算法，由 D.E.Knuth、V.R.Pratt 和 J.H.Morris 共同發現。核心思想：利用模式串內部的局部匹配信息，避免主串指針回溯，實現 O(n+m) 時間複雜度。

核心概念：next 數組（前綴函數）

next[j] 表示模式串 T[0...j-1] 中最長真前綴與真後綴的匹配長度。

數學定義

next[0] = -1
next[j] = max{ k | 0 < k < j 且 T[0...k-2] == T[j-k...j-1] }  (集合非空時)
next[j] = 0  (其他情況)

註：本文採用0 起始下標，與部分教材 1 起始不同。

樸素匹配 vs KMP 關鍵差異

特性	樸素匹配	KMP 算法
主串指針	失配後回溯到上次起始位置+1	從不回溯，始終向前
模式串指針	重置為 0	根據 `next` 跳轉
時間複雜度	O(n×m)	O(n+m)

標準版 KMP 代碼實現

#include <stdio.h>

void get_next(const char *T, int next[], int T_len)
{
    int i = 0, j = -1;
    next[0] = -1;

    while (i < T_len - 1) {
        if (j == -1 || T[i] == T[j]) {
            ++i; ++j;
            next[i] = j;  // 標準版：直接賦值
        } else {
            j = next[j];  // 失配跳轉
        }
    }
}

int Index_KMP(const char *S, const char *T, int pos)
{
    int next[255];
    int i = pos, j = 0;
    int T_length = 0;

    while (T[T_length] != '\0') T_length++;
    get_next(T, next, T_length);

    while (S[i] != '\0' && j != T_length) {
        if (j == -1 || S[i] == T[j]) {
            ++i; ++j;
        } else {
            j = next[j];
        }
    }

    if (j == T_length) return i - T_length;
    return -1;
}

int main()
{
    char *S = "abcacaabaaaecdeaaaabacdeabcd";
    char *T = "aaaa";
    printf("%d\n", Index_KMP(S, T, 0));
    return 0;
}

改進版 KMP（nextval 優化）

優化動機

標準版中，若 T[i] == T[next[i]]，則失配時跳轉到 next[i] 位置，但該位置字符與失配字符相同，必然再次失配，造成多餘比較。

改進邏輯

if (T[i] != T[j])
    next[i] = j;           // 不相等，保持原值
else
    next[i] = next[j];     // 相等，遞歸跳轉到 j 的 next 值

改進版 get_next 關鍵片段

if (j == -1 || T[i] == T[j]) {
    ++i; ++j;
    if (T[i] != T[j])       // 改進判斷
        next[i] = j;
    else
        next[i] = next[j];
} else {
    j = next[j];
}