KMP算法详解（C#实现高效字符串匹配）

KMP 算法的两个关键步骤

1. 构建 next 数组：预处理模式串，计算每个位置的最长公共前后缀长度。
2. 执行匹配：利用 next 数组在主串中高效查找模式串。

C# 实现 KMP 算法

下面我们用 C#语言 来完整实现 KMP 算法。代码分为两部分：生成 next 数组和执行字符串匹配。

using System;public class KmpMatcher{    /// <summary>    /// 构建 next 数组（部分匹配表）    /// </summary>    public static int[] BuildNext(string pattern)    {        int m = pattern.Length;        int[] next = new int[m];        next[0] = 0; // 第一个字符没有前缀/后缀        int j = 0; // j 表示当前最长公共前后缀长度        for (int i = 1; i < m; i++)        {            // 如果当前字符不匹配，回退 j            while (j > 0 && pattern[i] != pattern[j])            {                j = next[j - 1];            }            // 如果匹配，j 向前移动            if (pattern[i] == pattern[j])            {                j++;            }            next[i] = j;        }        return next;    }    /// <summary>    /// 使用 KMP 算法在主串中查找模式串    /// 返回首次匹配的起始索引，未找到返回 -1    /// </summary>    public static int KmpSearch(string text, string pattern)    {        if (string.IsNullOrEmpty(pattern))            return 0;        int n = text.Length;        int m = pattern.Length;        int[] next = BuildNext(pattern);        int j = 0; // 模式串指针        for (int i = 0; i < n; i++)        {            // 不匹配时，根据 next 数组跳转            while (j > 0 && text[i] != pattern[j])            {                j = next[j - 1];            }            // 匹配成功，j 向前移动            if (text[i] == pattern[j])            {                j++;            }            // 完全匹配            if (j == m)            {                return i - m + 1; // 返回起始位置            }        }        return -1; // 未找到    }    // 测试示例    public static void Main()    {        string text = "ABABDABACDABABCABCABC";        string pattern = "ABABCABC";        int index = KmpSearch(text, pattern);        Console.WriteLine($"模式串 '{pattern}' 在主串中的位置: {index}");        // 输出: 模式串 'ABABCABC' 在主串中的位置: 10    }}

代码解析

• BuildNext 方法：通过双指针技巧构建 next 数组。i 遍历模式串，j 记录当前最长公共前后缀长度。
• KmpSearch 方法：主匹配逻辑。当字符不匹配时，j = next[j - 1] 跳过已知不可能匹配的部分。
• 时间复杂度：构建 next 数组 O(m)，匹配过程 O(n)，总时间 O(n + m)。

总结

KMP算法是字符串查找算法中的经典代表，特别适合在大数据量下进行高效匹配。通过预处理模式串生成 next 数组，避免了主串指针回退，极大提升了性能。

对于 C# 开发者来说，掌握 KMP 算法不仅能提升算法能力，还能在实际项目中优化文本处理逻辑。无论是面试还是工程实践，C#字符串匹配中的 KMP 实现都是一项重要技能。

希望这篇教程能帮助你彻底理解 KMP 算法！如果你有任何问题，欢迎留言讨论。