KMP算法的C#实现方法

概述

KMP算法是一种字符串匹配算法，可以用于快速查找一个字符串是否包含另一个字符串，或者在多个字符串中查找某个子串。该算法的基本思想是尽可能地避免重复匹配。通过预处理模式串的匹配数组，我们可以在匹配过程中跳过已经匹配过的部分，从而提高匹配效率。

算法实现

步骤一：求取模式串的匹配数组

首先，我们需要对模式串进行预处理，求取出模式串的匹配数组 $next$，该数组记录了当前位置之前的子串中最长的相等前缀后缀的长度。

private static void getNext(string pattern, int[] next)
{
    int i = 0, j = -1;
    next[0] = -1;

    // 循环计算匹配数组
    while(i < pattern.Length - 1)
    {
        if(j == -1 || pattern[i] == pattern[j])
        {
            i++;
            j++;
            next[i] = j;
        }
        else
        {
            j = next[j];
        }
    }
}

步骤二：匹配主串和模式串

在匹配主串和模式串时，如果当前字符匹配成功，则进行下一位字符的匹配；否则，根据模式串的匹配数组，向前跳过一定长度的字符，继续匹配。

public static int KMP(string text, string pattern)
{
    int i = 0, j = 0;
    int[] next = new int[pattern.Length];

    // 求取匹配数组
    getNext(pattern, next);

    // 匹配主串和模式串
    while(i < text.Length && j < pattern.Length)
    {
        if(j == -1 || text[i] == pattern[j])
        {
            i++;
            j++;
        }
        else
        {
            j = next[j];
        }
    }

    // 匹配成功，返回匹配的起始位置；否则，返回 -1
    if(j == pattern.Length)
    {
        return i - j;
    }
    else
    {
        return -1;
    }
}

示例

假设我们要在字符串 "ABCABCABCABCDABCMN" 中查找子串 "ABCABD"，则代码实现如下：

string text = "ABCABCABCABCDABCMN";
string pattern = "ABCABD";

int index = KMP(text, pattern);
if(index != -1)
{
    Console.WriteLine("找到了，起始位置是：" + index);
}
else
{
    Console.WriteLine("没找到！");
}

假设我们要在多个字符串中查找某个子串，则代码实现如下：

string[] texts = {"ABCABCABCABCDABCMN", "DEFGABCABC", "HIJKLM"};
string pattern = "ABCABD";

foreach(string text in texts)
{
    int index = KMP(text, pattern);
    if(index != -1)
    {
        Console.WriteLine("在字符串" + text + "中找到了，起始位置是：" + index);
    }
    else
    {
        Console.WriteLine("在字符串" + text + "中没找到！");
    }
}

总结

KMP算法是一种高效的字符串匹配算法，可以在 $O(n+m)$ 的时间复杂度内完成匹配过程，其中 $n$ 和 $m$ 分别是主串和模式串的长度。实现该算法的关键在于预处理模式串的匹配数组，通过该数组在匹配过程中避免重复匹配，从而提高匹配效率。