拖了那么久的kmp算法这次终于要把它写完了，我也不知道我在学什么东西，这么能拖

BF

BF算法，即暴力匹配算法，时间复杂度O（nm）；
没什么讲的，代码：

for(int i=0,j=0;i<s.size();i++){
        if(s[i]==p[j]){
            ++i;
            ++j;
        }
        else {
            i=i-j+1;
            j=0;
        }
        if(j==p.size()){
            //匹配成功 
        } 
    } 

KMP匹配

在暴力算法中可以发现，字符串中有些信息是可以在利用的，在回溯的过程我们只需要回溯到s串后缀与p数组前缀相等的地方，之后再继续比较，可以降低之间复杂度
比如下面这个情况

可以直接移到后缀和前缀相等的地方，即j=next[j]

这些模板的next数组与真实next数组相差1
###从1下标开始写的代码

// s[]是长文本，p[]是模式串，n是s的长度，m是p的长度
//求模式串的Next数组：
//字符串从1开始
for (int i = 2, j = 0; i <= m; 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 <= n; i ++ )
{
    while (j && s[i] != p[j + 1]) j = ne[j];
    if (s[i] == p[j + 1]) j ++ ;
    if (j == m)
    {
        j = ne[j];
        // 匹配成功后的逻辑
    }
}

从0下标开始的代码

    ne[0]=-1;
    for(int i=1,j=-1;i<m;i++){
        while(j>=0&&p[i]!=p[j+1]) j=ne[j];
        if(p[j+1]==p[i]) j++;
        ne[i]=j;
    } 
    for(int i=0,j=-1;i<n;i++){
        while(j>=0&&s[i]!=p[j+1]) j=ne[j];
        if(s[i]==p[j+1]) j++;
        if(j==m-1){
            j=ne[j];//回溯最长相同前后缀的地方为下一次匹配做准备
               //匹配成功后按题意输出 
        }
    }

求next数组

求next数组其实跟kmp匹配一样，只不过是模式串自己匹配自己，需要让i，j；错开就可以匹配p字符串的前后缀，求出当前的最长长度，就是next的值。代码在上面
其实就是自己匹配自己，理解这个就能写代码了；

模板题：

KMP字符串匹配

代码：

#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
#define sc(n) scanf("%d",&n);
#define ios ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
typedef long long ll;
const int MOD=1000000007;
const int N=100010;
int a[N];
string s,p;
int ne[N]; 
int main(){
    //BF匹配算法 
//    string s,p;
//    for(int i=0,j=0;i<s.size();i++){
//        if(s[i]==p[j]){
//            ++i;
//            ++j;
//        }
//        else {
//            i=i-j+1;
//            j=0;
//        }
//        if(j==p.size()-1){
//            //匹配成功 
//        } 
//    } 
    string s,p;
    cin>>s>>p;
    int n=s.size();
    int m=p.size();
    ne[0]=-1;
    for(int i=1,j=-1;i<m;i++){
        while(j>=0&&p[i]!=p[j+1]) j=ne[j];
        if(p[j+1]==p[i]) j++;
        ne[i]=j;
    } 
    for(int i=0,j=-1;i<n;i++){
        while(j>=0&&s[i]!=p[j+1]) j=ne[j];
        if(s[i]==p[j+1]) j++;
        if(j==m-1){
            cout<<i-j+1<<endl;
            j=ne[j];//回溯最长相同前后缀的地方为下一次匹配做准备 
        }
    }
    for(int i=0;i<m;i++) cout<<ne[i]+1<<" "; 
    return 0;
}
/*
*/

注：每次匹配成功之后一次，j一定要回溯到next[j]的位置，