wiki 介绍

在计算机科学中，Knuth-Morris-Pratt字符串查找算法（简称为KMP算法）可在一个主文本字符串S内查找一个词W的出现位置。此算法通过运用对这个词在不匹配时本身就包含足够的信息来确定下一个匹配将在哪里开始的发现，从而避免重新检查先前匹配的字符。

思路

首先我们可以用常规思路去考虑如果自己实现一个这样的算法应该如何实现

主字符串:S
词:W

将两个字符串S和W进行匹配，分别从0，0位置开始匹配
当出现不匹配的情况，重新从1，0位置开始匹配，相当于跳过主字符串的第0位重新匹配一遍。
以此类推

这样的算法很容易可以看出需要O(n2)的时间复杂度，但是也很容易想到

那么KMP算法的时间复杂度是O(n) 是如何做到的呢？

我们再一次回顾刚刚的算法，我们进行优化，其中最需要优化的部分就是第2步：当不匹配的时候S跳过1位再重新匹配，这样会出现前面n位其实已经匹配了但是一旦只移1位会导致全部错位，我们更希望从最相似的地方开始重新匹配。这就是KMP算法。

部分匹配表(PMT)

所谓的部分匹配表，实际上表中存放的就是字符串前后缀公共字段最长长度值。

什么是前缀后缀

aba
前缀:a，ab
后缀:a，ba
也就是说，前/后缀是包含第一个/最后一个且不包含整个字符串的子序列。

上面的公共字段的最长长度值为1。

KMP算法

i：S的下标
j：W的下标

延续刚刚的思路，当出现不匹配的情况时，我们将S理解为前缀，W理解为后缀，这时候W应该移动到上一个相同的位置的最长最公共字段的位置。也就是j=PMT[j-1]

这样就避免了大量错位的情况，也使得算法的时间复杂度降到O(n)

下面是一组动图可以结合理解。

C++实现

vector<int> getNext(string& str)
{
    vector<int> next(str.size()+1);
    next[0]=-1;
    int i=0,j=-1;
    while(i<str.size())
    {
        if(j==-1||str[i]==str[j])
        {
            ++i;
            ++j;
            next[i]=j;
        }else
            j=next[j];
    }
    return next;
}
int KMP(string str1,string str2)
{
    int i=0,j=0;
    vector<int> next=getNext(str1);
    while(i<str1.size()&&j<str2.size())
    {
        if(j==-1||str1[i]==str2[j])
        {
            i++;
            j++;
        }else 
            j=next[j];
    }
    if(j==str2.size())
        return i-j;
    else
        return -1;
    
}