KMP算法接触是从滑动窗口的使用开始的，因为涉及到模式（字符串）匹配，自己也是理解了好久才差不多弄懂，写在了LeetCode题解里，直接复制过来，以作记录，唯一缺点就是没有图。 在187. 重复的DNA序列问题中，用到的是滑动窗口加目标串编码的方式，但是该问题中匹配串的长度可以很长，因此不适用于编码-增删位，从而一一对应。

本文缺点：没有图

结合别的大佬的图凑合看~

I. 一般思路

利用内置函数来操作

  • 使用C++中的内置函数substr(int begin, int length)，维护一个固定长度的窗口，每次取出窗口字符串与目标字符串比较，从而返回结果

朴素匹配法

  • 在总的字符串序列中，不断更新起始位置start，对于每个start，比较后续字符与目标字符串中是否一一相等，从而返回结果
  • 整体复杂度为 $O(n*(m-n))$，其中 $n$ 为目标字符串长度， $m$ 为总的字符串长度。

II. KMP 算法

如何更好地理解和掌握 KMP 算法? - 知乎

其实在朴素匹配法中，存在可以优化的地方，也就是当对于起始位置start的的后续匹配中，如果出现了与目标字符串不匹配的字符，目标字符串的索引不一定要回退到起始位置，从头开始，因为这中间有可能有一部分是匹配好的。

  • 最极端的例子，目标字符串中的所有字母都不一样，那么肯定需要从头开始
  • 假如目标字符串前几个都一样，aaaaf，而总的字符串为aaaaaaf，很显然，不需要对总字符串中的每个start，都将目标字符串从头开始

KMP算法要解决的问题

  • 因此，KMP算法解决的问题其实就是，当遇见不匹配的字符时，快速告诉我们目标字符串的索引应该回退到哪里? 开始位置？ where？

KMP算法用什么解决这个问题

部分匹配表(PMT表，Partial Match Table)）或者叫前缀表

  • PMT表中元素的含义：

  • PMT表如何解决快速定位回退位置的问题

    • 思考一个例子，总的字符串为string s1=abababcf，目标字符串为string s2=ababc。
    • 很显然，在第一轮匹配过程中s1[4]和s2[4]失配，按照朴素匹配的方法，s1的索引回退到索引 $1$，s2则回退到索引 $0$ 从头开始。
    • 但其实，肉眼观察可以看出s1和s2的索引都不需要回退到上述位置，而应该s1索引保持不变，s2索引回退到 $2$，为什么？可以从PMT表中得到这个信息吗？
    • 答案是可以的，具体来说。因为是在索引 $4$ 失配，则说明s1[0]到s1[3]和s2[0]到s2[3]是完全匹配的，二者分别记为ss1和ss2（内容为abab）。
    • 所以利用索引 $3$ 的PMT值，很容计算得到PMT[3]=2，也就是字符串abab的前缀集合（{a,ab,aba}）与后缀集合（{b,ab,bab}）的交集中最长元素（ab）的长度，即等于 $2$。
    • 这就意味着ss1的前 $2$ 个字符和ss1的后 $2$ 个字符是相同的，又因为ss1和ss2是相等的，则ss2的前 $2$ 个字符和ss1的后 $2$ 个字符是相同的（自己画个图会好理解点），那这个时候就只需要s1的索引保持不变（为$4$），s2的索引回退到 $2$（索引4回退2个位置得到的），然后继续匹配。
    • 因为s1从索引 $4$ 倒数两个字符和s2正数两个字符是相同的，因此可以跳过匹配。

PMT表$\to$ next数组

在上述的例子中，失配的索引是 $4$ ，但是我们关注的是 $PMT[3]$，为了方便起见，可以将 $PMT$表整体右移，对于 $PMT[0]$ 则赋值为 -1，就称为next数组。

III. next数组的计算

我个人觉得这个才是KMP算法中最难理解的地方，呜呜呜~

vector<int> getNext(string p)
{
    // 定义前后的指针
    int left=-1,right=0;
    // 匹配串的长度
    int n=p.size();
    // 返回的结果，即next数组，注意是next数组，不是PMT表，也就是PMT表右移一位的结果
    // 也就是说next[i]记录的是字符串 p[0]-p[i-1]的前后缀集合交集最大长度
    vector<int> next(n);
    next[0]=-1;
    while(right<n-1)  // 因为right=n-2时的计算结果，存储在next[n-1]中
    {
        // 如果left在最开始位置或者当前left索引值与right索引值相等
        // 那么从0到right的这段字符串的前后缀集合交集最大长度为left+1，且应该存储在next[right+1]中
        // 为什么要加这个left==-1这个条件呢，因为如果不加这个条件，left从零开始，right从1开始
        // 假如一开始就不相等，则else分支将索引出错，left=next[0]=-1,再次进入时，将索引错误
        if(left==-1 || p[left]==p[right])
        {
            left++;
            right++;
            next[right]=left;
        }
        // 如果不相等，且left也不是在-1位置，则left应该回退到一个特定位置
        // 此时left索引值与right索引值不匹配，类似于KMP的匹配机制一样
        // 根据已经生成的next表,next[left]保存的是 0到left-1的最长公共前后缀
        // 也就意味着 p[0]到p[left-1]字符串中的最大公共前后缀长度是 next[left]
        // 假设回退索引位置为 x，则应有 x-0=next[left]，即索引位置是next[left]
        else
        {

            left=next[left];
        }
    }
    return next;
}

总的来说

class Solution {
public:
    int strStr(string haystack, string needle) {
        // 尝试下KMP算法
        vector<int> next=getNext(needle);
        int left=0,right=0;
        int hLen=haystack.size(),nLen=needle.size();
        while(right<hLen)
        {
            char c=haystack[right];
            char t=needle[left];
            if(c==t)
            {
                left++;
                right++;
                // 相等之后，left走完needle字符串
                if(left==nLen)
                    return right-nLen;
            }
            else
            {
                if(left==0)
                    right++;
                else
                {
                    left=next[left];
                }
            }

        }
        return -1;
    }
    vector<int> getNext(string p)
    {
        int left=-1,right=0;
        int n=p.size();
        vector<int> next(n);
        next[0]=-1;
        while(right<n-1)
        {
            if(left==-1 || p[left]==p[right])
            {
                // 这一段表达的其实是 索引0到right的最大公共前后缀长度 left+1应该保存在next[rgiht+1]中
                // 为什么是left+1，因为left对应的是索引位置，是从零开始的
                left++;
                right++;
                next[right]=left;
            }
            else
            {
                // 否则回退到匹配好的位置，回退的是索引位置，回退的数目是next[left]，则从零开始索引
                // 假如，最大公共长度next[left]=2，意味着索引0、1是最大长度，应该继续从2开始匹配
                left=next[left];
            }
        }
        return next;
    }
};

参考链接

$\cdots$ end $\cdots$