VS KMP-串的模式匹配（五）

飞熊 • 2023年5月24日上午10:54 • 后端开发 • 阅读 74

　　
　　最近在复习软考的知识及概念，又有机会学习新的算法内容。在这个周末的晚上就和大家来分享一下我的总结吧。首先来看看它的介绍：
　　

引入：

　　子串的定位操作通常称为串的模式匹配，它是串处理系统中最重要的运算之一，子串常被称为模式串。它的基本思想是从主串的第一个字符起与模式串的第一个字符比较，若相等，则继续逐对字符进行后续的比较，否则从主串的第二个字符起与模式串的第一个字符重新比较，直到模式串中每个字符依次和主串中一个连续的字符序列相等为止，此时称为匹配成功。如果不能在主串中找到与模式串相同的子串，则匹配失败。以上是对朴素的模式匹配算法的描述。
　　然而在技术不断发展的当下，常会提起的是改进的模式匹配算法：KMP。下面让我开始KMP的学习~

书本介绍：

正文：

　　可以看到上图中给出了一个 Next【j】函数，这是KMP在之前模式匹配之上的改进处，通过函数的记录可以节省对比过程中的消耗。下面附上相关的C#代码：
　　

static int KMP(string s, string p)
        {
            int i, j;
            int[] next = new int[p.Length];
            Get_Next(p, next);
            i = 0;
            j = 0;
       while (i < s.Length && j < p.Length)
            {
                if (j == -1 || s[i] == p[j])
                {
                    ++i;
                    ++j;
                }
                else
                {
                    j = next[j];
                }
            }
            if (j == p.Length)
                return i - p.Length;
            return -1;
        }