KMP算法

ciye — Mon, 07 Jul 2025 15:53:08 +0800

1.求next数组
```
void get_next(int m) {
    ne[1]=0;
    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;
    }
}
```

2.KMP算法求匹配位置
```
void kmp(int n,int m) {
    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) cout<<i-m+1<<"\n";
    }
}
```

3.完整代码示例
题目：[P3375 【模板】KMP](https://www.luogu.com.cn/problem/P3375 "P3375 【模板】KMP")
```
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e6+10;

int ne[N];
string s,p;

void get_next(int m) {
    ne[1]=0;
    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;
    }
}

void kmp(int n,int m) {
    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) cout<<i-m+1<<"\n";
    }
}

void solve() {
    cin>>s>>p;
    s=' '+s;
    p=' '+p;
    get_next(p.size()-1);
    kmp(s.size()-1,p.size()-1);
    for(int i=1;i<p.size();i++) cout<<ne[i]<<" ";
}

signed main() {
    ios::sync_with_stdio(0),cin.tie(0);
    int T=1;
    //cin>>T;
    while(T--) {
        solve();
    }
    return 0;
}
```

裴蜀定理/贝祖定理

ciye — Fri, 04 Jul 2025 17:03:36 +0800

Ciyeblog - 2025年7月

KMP算法

裴蜀定理/贝祖定理