C# KMP 算法字符串匹配實現

KMP 算法完整實現：Next 陣列構建與匹配主流程

一、Next 陣列構建邏輯

next[0] = -1;
next[j] = max{ k | 0 < k < j && "t0t1...t(k-1)" == "t(j-k)t(j-k+1)...t(j-1)" };
next[j] = 0; // 若無符合條件 k

證明思路：假設模式串下一步移動到 k 位置，則：

1. 模式串前 k 字符 = 文本串 i 位置前 k 字符
2. 模式串 j 位置前 k 字符 = 文本串 i 位置前 k 字符
3. 推得：模式串前綴 (0~k-1) = 模式串後綴 (j-k~j-1)

二、匹配主流程

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 0; // 匹配失敗

核心優勢：文本指針 i 永不回退，時間複雜度 O(n+m)。