两种算法的区别：

黄线为已经匹配的部分，两段绿线为c之前相同的前后缀，当c失配时，分别从箭头位置开始匹配的效果是完全相同的。

暴力是从第一个箭头开始，KMP是从第二个开始，这就是两中方法的差别。（不知道能不能看懂）

一、暴力解决：

复杂度：O（N*M）

1、abab匹配成功，但当 i=4 (j=4) 时d与c失配。

2、令j=0，i=1重新开始匹配，当i=1(j=0)时失配，继续移动。

3、重复上面的步骤，知道最后匹配成功，输出起始位置。

代码模板：

void Search(string a,string p)
{
    int la=s.size(),lp=p.size();
    for(int i=0;i<la;i++){
        for(int j=0;j<lp;j++){
            if(a[i]!=p[j]){
                break;
            }
            if(j==lp-1){
                cout<<i<<endl;
            }
        }
    }
}

上面的复杂度确实很高，KMP算法的优点就是用线形的时间复杂度解决这个问题。

二、KMP算法

复杂度：O(N+M)

1、同样abab匹配成功，但当 i=4 (j=4) 时d与c失配。

2、此时令j=Next[j]，即j=Next[4]=2,i不变，继续比较，此时d与a失配。（先不要关心Next[4]=2什么意思，求Next数组传送门）

3、重复上面的步骤，直到最后完全匹配为止。

比较上面的两种方法应该能看出复杂度的曲别。

Next数组含义：

以p串为例子，它的每个坐标对应的Next数组的值如下：

Next数组的含义：Next[4]=2的含义就是 [0,3] 这个子串的前缀与后缀最大相同的字符数目为2。

求解Next数组：

先上代码（找了很多天，这个算是最好用的了）感谢：Venishel

///p[k]为前缀，p[i]为后缀
void getNext(string p,LL lp,LL Next[]){
    LL k=0;
    for(LL i=1;i<lp;i++){
        while(k&&p[i]!=p[k]) k=Next[k];
        if(p[i]==p[k]) k++;
        Next[i+1]=k;
    }
}

KMP算法匹配：

感谢： v_JULY_v

该字符对应的Next 值会告诉你下一步匹配中，j应该跳到哪个位置（跳到Next [j] 的位置）。如果Next [j] 等于0，则跳到p串的开头，若Next [j] 不为0，代表下次匹配跳到Next[j]的位置，而不是跳到开头，且具体跳过了j-Next[j] 个字符。

像下面的这种情况：

1、现在d与c失配：

2、Next[j]=2，即j跳到2的位置。

代码：

void kmp(string a,string p,LL la,LL lp){
    LL j=0;
    for(LL i=0;i<la;i++){
        while(j&&a[i]!=p[j]) j=Next[j];
        if(a[i]==p[j]) j++;
        if(j==lp) cnt++,j=0;
    }
}

KMP完整代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL MAX=1e6;
LL Next[MAX+5],cnt;
void getNext(string p,LL lp,LL Next[]){
    LL k=0;
    for(LL i=1;i<lp;i++){
        while(k&&p[i]!=p[k]) k=Next[k];
        if(p[i]==p[k]) k++;
        Next[i+1]=k;
    }
}
void kmp(string a,string p,LL la,LL lp){
    LL j=0;
    for(LL i=0;i<la;i++){
        while(j&&a[i]!=p[j]) j=Next[j];
        if(a[i]==p[j]) j++;
        if(j==lp) cnt++,j=0;
    }
}
int main()
{
    string a,p;
    cin>>a>>p;
    LL la=a.size(),lp=p.size();
    getNext(p,lp,Next);
    kmp(a,p,la,lp);
    cout<<cnt<<endl;
    return 0;
}