如何在C#中自己动手实现KMP字符串匹配算法？

KMP算法全称Knuth-Morris-Pratt，是一种线性时间的字符串匹配算法。与暴力算法每次失配后主串指针回退不同，KMP利用模式串自身结构生成部分匹配表，使主串指针只进不退，从而把最坏情况复杂度从O(n*m)降到O(n+m)。在C#里虽然没有内置KMP，但借助Span与数组完全可以写出高效且易读的实现。

一、KMP核心概念与Next数组原理

KMP的关键在于预处理模式串得到Next数组（也有资料称部分匹配表或失效函数）。Next[i]表示模式串子串pattern[0..i]中，最长的相等前缀与后缀的长度。当在位置i发生失配时，模式串不必从头比，而是滑动到Next[i-1]继续，主串索引不回退。

理解前缀与后缀很重要。前缀指不包含最后一个字符的连续头部，后缀指不包含第一个字符的连续尾部。例如在模式串"ABAB"中，前缀有"A"、"AB"、"ABA"，后缀有"B"、"AB"、"BAB"，最长公共前后缀是"AB"长度为2，所以Next[3]=2。这个数值直接决定失配时的回跳位置。

构建Next数组采用双指针法：用len记录当前最长公共前后缀长度，初始为0；i从1开始遍历模式串。若pattern[i]==pattern[len]，则len加一，Next[i]=len；否则若len不为0，令len=Next[len-1]继续比较，若len为0则Next[i]=0。该过程本身也是一次轻量KMP匹配。

// 计算KMP的Next数组
static int[] BuildNext(string pattern)
{
    int n = pattern.Length;
    int[] next = new int[n];
    int len = 0; // 当前最长公共前后缀长度
    int i = 1;
    while (i < n)
    {
        if (pattern[i] == pattern[len])
        {
            len++;
            next[i] = len;
            i++;
        }
        else
        {
            if (len != 0)
            {
                len = next[len - 1]; // 回退到更短的公共前后缀
            }
            else
            {
                next[i] = 0;
                i++;
            }
        }
    }
    return next;
}

二、C#中的KMP搜索方法实现

有了Next数组，搜索阶段就很简单。主串指针i与模式串指针j同时从0开始，字符相等则双进；若失配且j不为0，令j=Next[j-1]；若j为0且仍不等，i前进。当j等于模式串长度时，说明找到匹配，记录位置后可继续搜索后续出现。

下面给出完整搜索函数，返回所有匹配起始索引。使用List<int>收集结果，对大文本也可改为yield return以节省内存。注意Next[j-1]的索引边界，j为0时不能再回退，只能移动主串。

// 在文本中查找模式串所有出现位置
static List<int> KmpSearch(string text, string pattern)
{
    List<int> result = new List<int>();
    if (pattern.Length == 0) return result;
    int[] next = BuildNext(pattern);
    int i = 0; // 主串索引
    int j = 0; // 模式串索引
    while (i < text.Length)
    {
        if (text[i] == pattern[j])
        {
            i++;
            j++;
            if (j == pattern.Length)
            {
                result.Add(i - j); // 记录匹配起点
                j = next[j - 1];   // 继续寻找下一个匹配
            }
        }
        else
        {
            if (j != 0)
            {
                j = next[j - 1];
            }
            else
            {
                i++;
            }
        }
    }
    return result;
}

上述代码时间复杂度为O(n+m)，空间复杂度O(m)存储Next数组。在重复模式如"AAAA"中，Next值依次为0,1,2,3，失配时可快速大幅回跳，比IndexOf的逐字符回溯更高效。不过对于极短模式或随机文本，CLR内部优化过的IndexOf往往已足够快，KMP优势在长模式与高重复度场景才明显。

三、使用示例与边界情况处理

调用方式非常直观。下面演示在一段日志中找出所有错误标记位置，并输出索引。若模式串比文本长，应直接返回空列表，函数已隐含该逻辑因为j永远无法达到pattern.Length。

string log = "error: disk fullnerror: net downnok: done";
string pat = "error";
List<int> hits = KmpSearch(log, pat);
foreach (int pos in hits)
{
    Console.WriteLine("匹配位置: " + pos);
}
// 输出: 匹配位置: 0  匹配位置: 16

另一个易错点是在Next数组构建时若模式串含Unicode字符，C#的string索引仍按UTF-16代码单元处理，对普通中文英文无影响，但代理对字符需额外注意。生产环境可改用ReadOnlySpan<char>避免分配。若只需首次匹配，可在result.Add后直接return，省去后续扫描。

综上，在C#实现KMP并不复杂，重点是把Next数组的回退逻辑写对。掌握后不仅能应付算法面试，也可封装成文本检索工具，在需要多次匹配同一模式串时复用Next数组，进一步提升性能。

C#KMP_algorithmstring_matching修改时间：2026-08-04 13:51:26