C实现Knuth-Morris-Pratt字符串匹配算法详解

算法概述

Knuth-Morris-Pratt（KMP）算法是一种高效的字符串匹配算法，由Donald Knuth、Vaughan Pratt和James Morris于1977年共同提出。该算法通过预处理模式字符串（pattern）来构建部分匹配表（Partial Match Table），从而在匹配过程中避免不必要的回溯，显著提高了匹配效率。

算法优势

KMP算法相比朴素的字符串匹配算法具有明显优势：

• 时间复杂度为O(n + k)，其中n是文本长度，k是模式长度
• 预处理阶段只需要处理模式字符串，与文本无关
• 匹配过程中文本指针不会回溯

核心实现解析

1. 预处理阶段：构建最长前缀后缀表

public int[] FindLongestPrefixSuffixValues(string pat)
{
    var lps = new int[pat.Length];
    for (int i = 1, len = 0; i < pat.Length;)
    {
        if (pat[i] == pat[len])
        {
            len++;
            lps[i] = len;
            i++;
            continue;
        }

        if (len != 0)
        {
            len = lps[len - 1];
        }
        else
        {
            lps[i] = 0;
            i++;
        }
    }
    return lps;
}

该方法构建了一个名为lps（longest prefix suffix）的数组，其中每个元素表示模式字符串中对应位置之前子串的最长相同前后缀长度。例如：

• 模式"ABABC"的lps数组为[0, 0, 1, 2, 0]
• 模式"AABAAB"的lps数组为[0, 1, 0, 1, 2, 3]

2. 匹配阶段：利用lps表进行高效匹配

public IEnumerable<int> FindIndexes(string str, string pat)
{
    var lps = FindLongestPrefixSuffixValues(pat);

    for (int i = 0, j = 0; i < str.Length;)
    {
        if (pat[j] == str[i])
        {
            j++;
            i++;
        }

        if (j == pat.Length)
        {
            yield return i - j;
            j = lps[j - 1];
            continue;
        }

        if (i < str.Length && pat[j] != str[i])
        {
            if (j != 0)
            {
                j = lps[j - 1];
            }
            else
            {
                i += 1;
            }
        }
    }
}

匹配过程的关键点：

1. 当字符匹配时，同时移动文本和模式指针
2. 当整个模式匹配成功时，记录位置并利用lps表调整模式指针
3. 当字符不匹配时，根据lps表跳过已知匹配部分

使用示例

var kmp = new KnuthMorrisPrattSearcher();
string text = "ABABDABACDABABCABAB";
string pattern = "ABABCABAB";
var indexes = kmp.FindIndexes(text, pattern);

foreach (var index in indexes)
{
    Console.WriteLine($"Pattern found at index {index}");
}

性能分析

KMP算法的性能优势主要体现在：

1. 预处理阶段时间复杂度为O(k)，k为模式长度
2. 匹配阶段时间复杂度为O(n)，n为文本长度
3. 总体时间复杂度为O(n + k)，优于朴素算法的O(n×k)
4. 空间复杂度为O(k)，用于存储lps表

应用场景

KMP算法特别适合以下场景：

• 需要多次在同一个文本中搜索不同模式
• 模式字符串较长且具有重复子结构
• 对搜索性能要求较高的应用，如文本编辑器、IDE的搜索功能

总结

C#实现的KMP算法通过预处理构建lps表，在匹配过程中避免了不必要的回溯，显著提高了字符串匹配效率。理解lps表的构建原理和匹配过程中的指针移动规则是掌握该算法的关键。该实现简洁高效，可直接用于各种需要字符串匹配的场景。