最容易理解的KMP算法讲解

对于字符串的匹配问题，我们最先想到的肯定是BF(Brute Force)暴力算法
BF算法的思路就是：遍历模板串，判断模板串的当前字符是否与子串的第一个子串相等，如果相等的话，那么子串和模板串同时往后移动一位再次进行判断，当全部相同(子串匹配成功)或者匹配的某一个字符不相同，那么结束匹配。匹配成功或者某一个字符不相同，我们需要将子串复原，模板串后移一位，我们则判断模板串的下一个字符与子串的首字符是否相等，相等再继续往后判断，不相等则模板串往后移动一位。
以落谷题目给出的样例为例：

ABABABC (模板串)
ABA (子串)

首先我们先判断模板串的第一个字符与子串的第一个字符是否相等

按照上面的思路，如果相等则继续判断模板串的下一个字符与子串的下一个字符是否相等，相等则继续遍历


通过多次比较发现我们在模板串第一个字符就匹配成功。匹配成功之后，继续查找是否还存在子串，这时候我们需要将字符复原，从头开始，模板串的话后移一位与子串的第一个字符进行比较。

比较发现首字符不匹配，所以匹配失败，那么模板串继续后移一位。

比较发现首字符匹配，则继续比较后面的字符，发现子串匹配成功，那么我们找到了第二个可以匹配成功的位置，为模板的第三个字符。然后我们将子串复原，模板串后移一位。

发现首字符不匹配，匹配失败，模板串继续后移一位。

模板串当前字符与子串的首字符相等，则继续往后匹配，发现第二个字符也相等，那么继续往后匹配，但是，到第三个字符发现不匹配，那么则匹配失败。子串复原，从头开始，模板串后移一位。

此时，模板串的长度已不满足子串的存在，所以没有必要再进行判断。直接结束匹配即可。

通过上述分析可知，我们找到了模板串的两个点满足子串匹配，第一个点是第一个字符，第二个点是第三个字符，与正确答案一致。那么下面通过代码来实现一下BF算法。

#include<iostream>
#include<string>
using namespace std;
int main(){
    string s,p;//s为模板串，p为子串
    cin>>s>>p;
    //遍历模板串，将模板串的每一个字符与子串的第一个字符进行比较
    //满足则往后继续比较，不满足或者完成匹配则比较模板串的下一个字符
    for(int i=0;i<s.size();i++){
        int j=0,tmp=i;
        //完全匹配或者模板串不够长结束匹配
        for(;j<p.size()&&tmp<s.size();j++,tmp++){
            //如果当前字符不相等则结束匹配
            if(p[j]!=s[tmp]){
                break;
            }
        }
        //如果比较的长度大于子串的长度(因为下标从0开始)，表示成功匹配
        if(j==p.size()){
            cout<<i+1<<endl;
        }
    }
    return 0;
}

通过代码分析时间复杂度，时间复杂度与模板串的长度(n)和子串的长度(m)有关,时间复杂度为O(nm)，一般的OJ给出的n、m的长度最大值为1e6(也就是10的6次方)，那么最坏的情况下要执行是1e12比较，c++一般情况1s可以执行1e9次比较。因此，使用BF算法无法完美解决字符串匹配问题。这个时候就引入了KMP算法。之所以称为KMP是因为这个算法是由3个人共同发明的，他们3个人的名字分别为Knuth、Morris和Pratt。这个算法比较难理解，网上也有很多的解释。但是，大多是人写的也是耐人寻味。KMP算法可以理解为是基于BF算法的优化版。
还是以上面的数据为例

ABABABC (模板串)
ABA (子串)

通过第一次比较我们找到了第一次子串在模板串中出现的位置，同时我们还知道了模板串的前3个字符，并且知道了第3个字符与子串的第一个字符是相等的，那么我们下次直接从第3个字符开始比较即可，不用再与第二个字符进行比较。这样我们就利用了已知的信息，不要把“搜索位置”移动到比较过的位置，继续往后移动，这样就提高了搜索的效率。
那么应该怎么做到这一点呢？我们可以针对要搜索的词，列出一张搜索表。这张表示怎么产生的后面具体阐述。

匹配成功之后发现最后一个字符对应的匹配值是1，表示最后面和最前面有1字符个是完全一样的，因此直接把模板串后移两位即可。因此得到公式：

移动位数 = 已匹配的字符数 - 对应的匹配值

下面模拟匹配的过程

然后介绍一下匹配值是如何产生的。
首先需要了解一下什么是前缀和后缀。"前缀"指除了最后一个字符以外，一个字符串的全部头部组合；"后缀"指除了第一个字符以外，一个字符串的全部尾部组合。
以"ABCDABD"为例
"ABCDABD"的前缀为[A, AB, ABC, ABCD, ABCDA, ABCDAB]
"ABCDABD"的后缀为[BCDABD, CDABD, DABD, ABD, BD, D]
“匹配值”就是“前缀”和“后缀”的最长的共有元素的长度。
上面的子串“ABA”为例

“A”的前缀和后缀都为为空集，共有元素的长度为0
“AB”的前缀为[A]，后缀为[B]，共有元素的长度为0
“ABA”的前缀为[A,AB]，后缀为[BA,A]，共有元素的长度为1

在代码中，匹配值就是传说中的next数组。很多同学对于求解next不是很理解。

通过上面的分析可知匹配值就是求子串的最长公共前后缀，与模板串无关。我们可以设置两个指针用来表示子串每部分的最长公共前后缀。
输入的两个字符串下标都从1开始(具体原因下面阐述)
子串的第一个子串是一个字符，不存在前后缀，所以直接从第二个子串也就是两个字符开始判断。以"ABCDABD"为例。
头指针初始应该指向下标为0的地方，头指针表示最长公共前后缀的前缀的最后一个字符，头指针的位置即表示匹配值
尾指针指向子串的部分子串的最后一个字符。
“AB”不存在相等前后缀，尾指针后移
“ABC”不存在相等前后缀，尾指针后移
“ABCD”不存在相等前后缀，尾指针后移
“ABCDA”存在相等前后缀，判断头指针指向的下一个字符是否与新增的字符相等，相等的话，头指针后移，尾指针后移，此时第2个“A”的值为1，也就是匹配值为1
“ABCDAB”存在相等前后缀，同理，此时第二个“B”的匹配值为2，存在公共前后缀“AB”
“ABCDABD”不存在相等公共前后缀。前缀“AB”的下一个字符“C”与新增的字符“D”进行比较，不相等，则将之前的前缀“AB”进行回溯，往回找，判断前缀“AB”的前缀子串是否有与新增“D”的后缀串存在相等的情况。例如：ABCABDABCABC，对于子串“ABCABDABCAB”新增字符“C”这种情况就是将前缀串“ABCABD”进行回溯(就是往回找),此时“ABCABDABCAB”对应的匹配值为“0 0 0 1 2 0 1 2 3 4 5”，先返回到位置5，然后判断“D”和新增的“C”是否相等，不相等的话就返回到位置2，然后再进行判断子串前缀的下一个字符“C”和新增的“C”是否相等，相等的话则新增的“C”的对应的匹配值则为3。

因此“ABCDABD”对应的匹配值为“0 0 0 1 2 0 1 2 3 4 5 3”
以上就是求解next数组的思路。通过上面的分析可知，如果输入的字符串从下标0开始的话，头指针初始会指向-1，进行回溯的话-1可能会作为数组的下标，因此对于匹配值为-1的情况需要特判，为了避免这些问题，建议下标从1开始。
子串和模板串匹配与求next数组过程非常相似，如果已知的部分模板串(已经与子串进行过匹配，部分成功匹配或者是成功匹配的模板串区间)和子串的前缀串不相等，则再继续找子串的前缀串的前缀串…。找到公共前缀子串后，子串和模板串同时后移，继续判断剩下的字符是否相等。如果未找到公共前缀子串，那么子串则从头开始与模板串进行比较。因此分析可知，KMP的时间复杂度是O(m+n)。

#include<iostream>
#include<string>
#include<cstring>
using namespace std;
char s[1000010],p[1000010];
//c++中有些头文件中存在关键字next，因此避免使用这个next变量名称
int ne[1000010];
int main(){
    //建议下标从1开始，因为从0开始需要考虑的多点，较麻烦
    cin>>s+1>>p+1;
    int ls=strlen(s+1),lp=strlen(p+1);
    for(int i=2,j=0;i<=lp;i++){
        while(j&&p[i]!=p[j+1]) j=ne[j];
        if(p[i]==p[j+1]) j++;
        ne[i]=j;
    }
    for(int i=1,j=0;i<=ls;i++){
        while(j&&s[i]!=p[j+1]) j=ne[j];
        if(s[i]==p[j+1]) j++;
        if(j==lp) cout<<i-lp+1<<endl;
    }
    //打印next数组
//    for(int i=1;i<=lp;i++) cout<<ne[i]<<" ";
    return 0;
}