C#利用KPM算法解决字符串匹配问题详解

什么是KMP算法

KMP算法（即Knuth-Morris-Pratt算法）是由 Donald Knuth、Vaughan Pratt、James H. Morris 同学在1977年联合发表的一种字符串匹配算法，主要用于在一个长文本串（缀）内查找一个模式串（子串）的出现位置。

该算法的核心思想是“利用已知信息尽可能减少不必要的匹配操作”，即利用模式串中已经匹配的前缀和后缀的关系，消除了“文本指针不回溯，模式串指针回溯”的操作，从而达到提高匹配效率的目的。该算法的时间复杂度为$O(m+n)$。

算法实现

下面是KMP算法的核心代码实现，其中txt代表长文本串，pat代表模式串，next数组即为模式串中每个字符对应的最长可匹配前后缀长度数组。

public static int KMP(string txt, string pat)
{
    int i = 0, j = 0, m = txt.Length, n = pat.Length;
    int[] next = GetNext(pat);

    while (i < m && j < n)
    {
        if (j == -1 || txt[i] == pat[j])
        {
            i++;
            j++;
        }
        else
        {
            j = next[j];
        }
    }

    if (j == n)
    {
        return i - j;
    }
    else
    {
        return -1;  // 未找到
    }
}

private static int[] GetNext(string pat)
{
    int[] next = new int[pat.Length];
    int i = 0, j = -1;

    next[0] = -1;

    while (i < pat.Length - 1)
    {
        if (j == -1 || pat[i] == pat[j])
        {
            i++;
            j++;
            next[i] = j;
        }
        else
        {
            j = next[j];
        }
    }

    return next;
}

示例说明

下面分别以“ABCDABD”和“mississippi”为文本串，以“ABD”和“issip”为模式串，来演示KMP算法的匹配过程。

第一组示例

长文本串：ABCDABD

模式串：ABD

执行KMP算法匹配后，输出0，即模式串ABD在长文本串中的起始位置是0。

第二组示例

长文本串：mississippi

模式串：issip

执行KMP算法匹配后，输出4，即模式串issip在长文本串中的起始位置是4。

总结

KMP算法是一种高效的字符串匹配算法，其核心思想是“利用已知信息尽可能减少不必要的匹配操作”，通过对模式串中最长匹配前后缀长度的计算，实现了匹配过程的快速搜索和跳转，避免了回溯操作带来的性能影响。在实际应用中，KMP算法常常用于文本编辑器、代码编辑器、搜索引擎、字典匹配、音频识别等场景，具有广泛的应用前景和深远的意义。