KMP算法的探索

KMP是字符串比对中一种高效的算法，在数据结构课堂上时间短很难完全理解。
于是课后我又自己摸索了一番，根据自己的理解独立编写了程序

规定

为了下文叙述方便先规定几个统一的说法：

文本串：被比对的字符串；
模式串：比对的模板字符串；
指针i：指向文本串正在比对位置的指针；
一系列指针：下文结合程序注释；
next数组、两种字符串下标均从1开始；

BF-算法

字符串比对中的暴力算法，没啥好说的，文本串逐位与模式串进行比较，不匹配则指针i回溯。例如：从i=1开始匹配，匹配到i=5时失败，回溯至i=2重新匹配。

next数组

关于KMP算法中最核心的思想蕴含在next[]数组中，next数组下标对应着字符串下标（下标从1开始，0位空置，至少我是空置）。顾名思义，next数组的值意义为本次“失配”后，下次匹配开始的位置（模式串的下标）。

思想动画

图A:源自于B站视频

图B:源自于B站视频

从图A到图B：第六位A失配后，很明显模式串发生了向右的滑动。
滑动的依据：滑动前箭头左侧的模式串前缀“AB”与后缀“AB”完全一致，由于箭头左侧已经匹配成功，所以对应的文本串也是一样的。这时候向右滑动既保证与文本串匹配，又避免了（滑动后）箭头左侧重复匹配操作。
滑动位数：即next数组的值。图中若以next数组表示，即位next[3] = 3。

两个‘3’均指模式串的第三位。翻译过来就是：当模式串中的第三位失配时，下一步从模式串的第三位继续匹配。

进一步抽象：有数组 next[x] = y，意思是：当模式串中的第x位失配时，下一步从模式串的第y位继续匹配。

上述 next[x] = y ，x没什么好说的就是模式串下标，下一步匹配位置y是如何得到的呢？
根据上图可以稍微总结一下：失配位置（箭头）左侧模式串前后缀一致的长度L加1，就是y。这个也很好理解，相当于我长度为L的子串已经匹配好了，那么只需要从L+1处继续匹配就好啦。

图片源于B站

这张图意在说明，在我们找一致的前后缀（很多人称为公共前后缀）的时候，是可能发生重叠的。

如果以上内容你看懂了

你就理解了next数组的求法了：即找出失配位置前，模式串子串的公共前后缀的最大长度L，并从L+1位开始继续匹配。

void cal_nextValue()
    {
        string t = compstr;
        int m = 0; //记录能够匹配的公共前后缀的最大长度
        if (t.size() <= 0) return;
        next[1] = 0; //模式串第一位直接置0，该位置左侧子串长度为0
        if (t.size() <= 1) return;
        next[2] = 1;//第二位失配了，左侧最大公共前后缀只能为1
         //从第三位开始，在失配位置左侧字符串寻找最长子串为公共前后缀
        for (int i = 3; i < t.size(); i++)
        {
           // j为“左挡板”往右移动限定后缀,k为“右挡板”往左移动限定前缀
            for (int k = i - 2, j = 2; j < i; j++, k--)
            {
                int flag = 1;
                int j_ = j; //不改变挡板位置
              //后缀与前缀进行比较
                for (m = 1; m <= k && j_ < i; m++, j_++)
                {
                  //字符不同则跳出循环，移动挡板位置（缩小前后缀长度）重新比较
                    if (t[j_] != t[m])
                    {
                        flag = 0;
                        break;
                    }
                }
                if (flag) break;
            }                 
             //循环结束时，由于for循环种“m++”实际匹配的最长公共前后缀为m-1；
            next[i] = m; //从最长公共前后缀下一位继续匹配，即 m-1+1=m
        }

看下来我们会发现next数组的求解与文本串没有关系，任何模式串都可以求出自己的next数组

比较字符串

其实next数组求解完了，比较字符串就很简单了。
先定义i和j两个指针：i指向文本串；j指向模式串。
第一次仍是逐一比较，相同则i、j均右移一位。当出现失配时，i不右移也不回溯，j根据next[j]的值移动，让移动后的模式串继续与第i位匹配比较。
（当指针j回退至0时，指针i、j需同时++。即若主串的第i个字符和模式的第1个字符不等，应从主串的第i+1个字符重新匹配）
循环结束后根据i、j指针位置即可判断

void cal_KMP()
    {
        cal_nextValue();
        if (tempstr.size() < compstr.size())
            return;

        int i = 1;
        int j = 1;
        while (i < tempstr.size() && j < compstr.size())
        {

            if ((tempstr[i] != compstr[j]) && next[j] != 0)
                j = next[j];
            else
            {
                i++;
                j++;
            }
        }
        if (j == compstr.size()) //匹配成功
        {
            result.didhave = true;
            result.pos = i + 1 - (compstr.size()-1);
        }
        else if (i == tempstr.size() && j != compstr.size()) //匹配失败
        {
            result.didhave = false;
            result.pos = -1;
        }
    }

教材简洁版

当我自己摸索完去看了眼教材，发现上面求next数组的程序好短

void get_next(SString T, int next[]){
  //T位模式串
  i = 1;
  next[1] = 0;
  j = 0;
  while(i < T[0]){
    if(j == 0 || T[i] == T[j]){
      ++i;
      ++j;
      next[i] = j;  
    }  
    else  j = next[j];
  }
}

T[0]应该是存放字符串长度的
有一说一我脑子不好挺难看懂。。放着有大佬会的也可以说说

KMP算法