KMP简单字符串匹配算法TOC讲解，逻辑清晰

1：背景TOC

给定一个基本字符串（用S替换）和一个模式字符串（用P替换），需要找到P的出现.在S位置，即字符串匹配问题。今天我们将介绍解决这个问题的常用算法之一，Knuth-莫里斯-普拉特算法（简称KMP）。这个算法是由高德纳（唐纳德·欧文·Knuth）和沃恩·普拉特于1974年创建的。同年，詹姆斯·H·莫里斯也开发了该算法，最终于1977年三人发表。
在继续之前，有必要介绍一下以下两点：后缀和后缀。

从上图中，“前缀”是指除最后一个字符之外的所有字符串开头； “后缀”是指字符串尾部除去第一个字符的组合。

2：Naive字符串匹配算法TOC

当我们第一次遇到字符串匹配问题时，我们脑子里的第一反应一定是连接一个简单的字符串（强绑定），即去遍历S的属性各至此。该字符与 P 进行比较，如果发出所有匹配项，则这将是结果；代码如下：

/* 字符串下标始于0 */
int NaiveStringSearch(string S, string P)
{
    int i = 0;    //S的下标
    int j = 0;    //P的下标
    int s_len = S.size();
    int p_len = P.size();

    while (i < s_len && j < p_len)
    {
        if (S[i] == P[j])  //若相等，都前进一步
        {
            i++;
            j++;
        }
        else  //不相等
        {
            i = i - j + 1;
            j = 0;
        }
    }

    if (j == p_len)  //匹配成功
        return i - j;

    return -1;
}

上述算法的时间复杂度为O(nm)，其中n为S的长度，m为P的长度。这次是很难满足我们的需求。咱们进入正题：时间复杂度为θ(n+m)的KMP算法。

三：KMP TOC字符串匹配算法

3.1 TOC流算法

（1）
 DA 首先，对字符串ABC DAB的第一个字符ABCBCA“BD”的第一个字符进行比较。由于 B 和 A 不匹配，因此模式字符串返回到一个位置。
(2)
 由于 B 和 A 不匹配，因此模式字符串反转。
(3)
 如此，直到主字符串与模式字符串的第一个字符相同。
(4)
再对比一下主绳和花绳的以下特征，还是一样的。
(5)
直到主字符串中出现与模式字符串的匹配字符不同的字符。
(6)
  此时，最自然的行为就是将整个模式字符串移动到一个位置，并从头开始逐一进行比较。虽然这是可能的，但是效率非常低，因为“位置搜索”必须移动到已经比较过的位置并再次比较。
(7)
  基本事实是，当空格不匹配 D 时，你知道前六个字符是“ABCDAB”。 KMP算法的思想是尝试利用这些已知信息，而不是将“搜索点”移回比较位置，而是继续移动它，从而提高其性能。
(8)

如何做到这一点？您可以为模式字符串设置跳转列 int next [ ]。稍后将展示如何计算这个数字。关于它的使用，您需要了解的内容很好。
(9)
 当已知空格和 D 不匹配时，前六个字符“ABCDAB”匹配。根据跳转顺序可以看出，不匹配的旁边的D的值为2，因此下一个从脚本位置2开始匹配。
（10）。 A、这里的next值为-1，表示模式串的第一个字符没有匹配到，所以直接返回一个位置。
(12)
  逐步比较，直至发现C和D不匹配，因此下一步从索引2开始匹配。
(13)
 逐级比较，直到发现模式串的最后一位数字匹配良好，则搜索完成。

3.2 next TOC的计算方法

next 数组解法是基于“前缀”和“后缀”，即next [j]与

0]相同... P[j-1]相同后缀中最长的（请先跳过j等于0的情况，下面会有解释）。我们仍以上表为例。为了方便阅读，我将其复制如下。 j 0 1 2 3 4 5 6 7 模型字符串 A B C D A♷A♷A 0 1 2 3 4 5 6 7 A A B C D next[j ] -1 0 0 0 0 1 2 0 (1) j=0，对于模式字符串的第一个字符，它与 组合下一个[0]=-1; (2) j=1，前面的字符串为A，最长等效后缀长度为0，即next[1]=0♽ ; (3) j=2，前一个字符。 (4) j=3，前一个字符串为ABC，最长等效后缀为0，即next[3]=0♽;; (5) j=4，前一串为ABCD ，相同前后缀最长为0，即next[4]=0； (6) j=5，前一个字符串为 ABCDA ，最长等效后缀为A，即，即 ，即 ，即 ，即♻； （7）j=6，前一串是ABCDAB，最长的后缀和后缀是AB，即AB，即 2； (8) j=7，前一个字符串为 ABCDABD，最长等效后缀长度为0，即next[7]=0❀ 那么，为什么在后缀长度与最长不一样的情况下也能跳转呢？例如，如果 j=6 不匹配，那么我们知道其位置之前的字符串是 ABCDAB。如果你仔细观察这个字符串，你会发现开头和结尾都有一个字符串。 A AB，由于j=6的D不匹配，我们不如直接取j=2的C，然后继续比较。因为有AB，而这个AB是类似于ABCDABABCDAB的最长后缀。 有些读者可能会有疑问。如果当 j=5 时匹配失败，正如我所解释的，则应取出并继续 j=1 中的字符。比较一下，但是两个地方的字符都是一样的，都是B。既然是一样的，那不就没有什么比较的意义了吗？其实并不是我的解释有问题，这个算法也没有问题，而是这个算法还没有编程。下面详细解释了这个问题，但我建议读者不要陷入困境并跳过这一点。稍后你就会明白。 思路很简单，接下来的问题就是实现代码了，如下： /* P为模式串，下标从0开始 */ void GetNext(string P, int next[]) { int p_len = P.size(); int i = 0; //P的下标 int j = -1; //相同前后缀的长度 next[0] = -1; while (i < p_len) { if (j == -1 || P[i] == P[j]) { i++; j++; next[i] = j; } else j = next[j]; } } 我很困惑吧？ 。 。 上面的代码是求每个位置的下一个值，即求每个位置之前字符串中最长的等价后缀的长度。为了下面详细分析，我将代码分为3部分： (1) i 的作用是什么？ i 是模式串 P 的表示，从 0 开始。在程序中，我们看到的值在序列中位于[i]之后。这很简单。 (2) j 的函数是什么？ 从next[i]=j;很容易理解，j表示前缀和后缀的最长公共元素的长度。 (3) if...else 语句...该怎么办？ 首先我们要弄清楚情况：如果此时i=3，那么接下来我们需要解决的是P[0]...p[3 ] 等效后缀长度为 next[4]，而不是 next[3]。这可以通过下面的代码来证明： i++; j++; next[i] = j; 下面详细分析这个事实：   假设 i 和 j 的位置如上所示，则由 [i]ne 得到=j ，即对于位置 i，分布 从 0 到 i -1 的最长等效后缀为 0 到 j-1 -1，即，两个部分的内容是相同的。 根据算法流程，if(P[i]==P[j])，则 i++;j++;next[i]=j;♽; 如果不是等于 j=next[j]，见下图： 按照 [j] j-1 划分相同后缀的长度最长的如图所示，由左侧两个椭圆表示，即这两个椭圆表示的部分内容相同；同样，右侧有两个相同的椭圆。因此，另一个语句使用第一个椭圆和第四个椭圆的内容来加速获得等于 0 到 i-1 的后缀长度。 向好朋友请教if语句中的j==-1是什么意思？首先，程序简单运行时，j初始化为-1，直接判断P[i]==P[j]无疑会报错；其次，在另一个语句中，j= next[j]，j 始终向后。如果向后移动时给j赋值-1（即j=next[0]），在P[i]==P[j]判断也会报错。总结以上两点，意义就是为了一个专门的边境法庭。 ？ A	B	D	'\0'
next[j]	-1	0	0	0	0	1	2	0

以中的上表为例♽ 如果采用以 › 为例。 j=5 匹配失败。根据3.2中的代码，现在应该取出j=1中的字符继续比较，但这两个位置上的字符是相同的，都是 B 。既然是一样的，那不就没有什么比较的意义了吗？我已经在 3.2 中对此进行了解释。这是因为 KMP 并不完美。那么我们该如何重写代码来解决这个问题呢？这很简单。

/* P为模式串，下标从0开始 */
void GetNextval(string P, int nextval[])
{
    int p_len = P.size();
    int i = 0;   //P的下标
    int j = -1;  //相同前后缀的长度
    nextval[0] = -1;

    while (i < p_len)
    {
        if (j == -1 || P[i] == P[j])
        {
            i++;
            j++;
            if (P[i] != P[j])
                nextval[i] = j;
            else
                nextval[i] = nextval[j];  //既然相同就继续往前找前缀
        }
        else
            j = nextval[j];
    }
}

还想提醒读者，KMP算法完全分为KMP算法（未优化版本）和KMP算法（优化版本），所以请读者在描述KMP算法时告知其版本。 ，由于两者在某些情况下有很大不同，我们在这里简单讨论一下。
KMP 算法（非优化版本）： 下一个序列表示最长等效后缀的长度。我们不仅可以使用以下方法来解决模式字符串匹配问题，还可以解决相似字符串、重复查询等问题。这些类型的问题你都可以在大型OJ中找到，所以我在这里不再赘述。
KMP算法（优化版）：在代码中易于识别（也改名为nextval）。接下来优化的表示相同的后缀长度，但是不一定是最长的（我个人称之为“最佳等价后缀”）。现在，我们可以使用以下优化的版本来更快地响应与模式字符串相关的问题（与非优化版本相比）。但优化后的版本并不能解决上面提到的字符串重复问题。
因此，使用哪个版本取决于您实际处理的实际问题。

参考文献：
[1] 严伟民.数据结构（C版）
[2]阮一峰.字符串匹配的KMP算法