C# KMP 字串比對演算法完整實作與原理詳解

問題定義

在字串 s 中，從位置 pos 開始，尋找第一個與目標字串 t 相符的子字串起始位置。

KMP 演算法核心思想

避免暴力比對中的重複回溯，利用目標字串 t 內部的「前綴 = 後綴」特性，預先計算 next 陣列（又稱失敗函數），比對失敗時直接跳轉，不需移動主字串指標。

步驟一：預處理計算 next 陣列

定義：

next[0] = -1;
next[j] = max{ k | 0 < k < j 且 "t0 t1 ... t(k-1)" == "t(j-k) t(j-k+1) ... t(j-1)" };
若無符合則 next[j] = 0;

數學證明

假設目標字串下一次移動到位置 k，則 k 之前的所有字元（共 k 個）應與主字串 s 中 i 位置前的 k 個字元相同：

"t0 t1 ... t(k-1)" == "s(i-k) s(i-k+1) ... s(i-1)"

同時，主字串 i 位置前的 k 個字元也等於目標字串 j 位置前的 k 個字元：

"t(j-k) t(j-k+1) ... t(j-1)" == "s(i-k) s(i-k+1) ... s(i-1)"

推得結論：

"t0 t1 ... t(k-1)" == "t(j-k) t(j-k+1) ... t(j-1)"

即目標字串的前綴等於以 j 為終點的後綴。

步驟二：比對主迴圈

while (s[i] != '\0' && t[j] != '\0')
{
    if (j == -1 || s[i] == t[j])  // j==-1 表示 s[i] 與 t[0] 不同
    {
        i++;
        j++;
    }
    else
    {
        j = next[j];  // 失敗跳轉
    }
}

if (t[j] == '\0')
    return i - j;  // 找到，返回起始位置
else
    return -1;     // 未找到

C# 完整實作

using System;

public class KMPMatcher
{
    /// 

    /// 計算 KMP 失敗函數陣列
    /// 
    public static int[] ComputeNextArray(string pattern)
    {
        int m = pattern.Length;
        int[] next = new int[m];
        next[0] = -1;
        int k = -1;
        for (int j = 1; j < m; j++)
        {
            while (k >= 0 && pattern[k + 1] != pattern[j])
                k = next[k];
            if (pattern[k + 1] == pattern[j])
                k++;
            next[j] = k;
        }
        return next;
    }

    /// 

    /// KMP 搜尋，返回首次匹配的起始索引，未找到返回 -1
    /// 
    public static int Search(string text, string pattern)
    {
        if (string.IsNullOrEmpty(pattern)) return 0;
        if (string.IsNullOrEmpty(text)) return -1;

        int[] next = ComputeNextArray(pattern);
        int n = text.Length;
        int m = pattern.Length;
        int i = 0, j = 0;

        while (i < n && j < m)
        {
            if (j == -1 || text[i] == pattern[j])
            {
                i++;
                j++;
            }
            else
            {
                j = next[j] + 1;  // 注意：這裡 next 定義與標準教科書略異，需對應調整
            }
        }

        return (j == m) ? i - m : -1;
    }
}

// 使用範例
class Program
{
    static void Main()
    {
        string text = "ABABDABACDABABCABAB";
        string pattern = "ABABCABAB";
        int pos = KMPMatcher.Search(text, pattern);
        Console.WriteLine(pos >= 0 ? $"找到於索引 {pos}" : "未找到");
    }
}

複雜度分析

• 時間複雜度：O(n + m)，其中 n 為主字串長度，m 為模式字串長度。
• 空間複雜度：O(m) 用於儲存 next 陣列。

關鍵優勢

主字串指標 i 永不回溯，適合串流資料或大量文字搜尋場景。