---
title: "KMP"
created: 2025-11-28
tags:
  - 算法
---

# KMP

## 分析

- [[2-Learning/02-算法/03-刷题理模型/串相关模型/KMP/KMP|KMP]]

只是kmp的话不算难 但它难在好多变形 要非常深入理解很多细节……

从1开始：

```cpp
#include <bits/stdc++.h>
using namespace std;

const int N = 100010, M = 1000010;

int n, m;
int ne[N];
char s[M], p[N];

int main()
{
    cin >> n >> p + 1 >> m >> s + 1;

    for (int i = 2, j = 0; i <= n; 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 <= m; i ++ )
    {
        while (j && s[i] != p[j + 1])
            j = ne[j];
        if (s[i] == p[j + 1])
            j ++ ;
        if (j == n)
        {
            //匹配成功的操作
            //printf("%d ", i - n);
            //……
            j = ne[j];//还原现场 因情况而定 可以省略 也可能是从头开始 j=0;
        }
    }
    return 0;
}
```

从0开始

```cpp
#include <bits/stdc++.h>
using namespace std;

const int N = 1000010;

int n, m;
char s[N], p[N];
int ne[N];

int main()
{
    cin >> m >> p >> n >> s;

    ne[0] = -1;
    for (int i = 1, j = -1; i < m; i ++ )
    {
        while (j >= 0 && p[j + 1] != p[i])
            j = ne[j];
        if (p[j + 1] == p[i])
            j ++ ;
        ne[i] = j;
    }

    for (int i = 0, j = -1; i < n; i ++ )
    {
        while (j != -1 && s[i] != p[j + 1])
            j = ne[j];
        if (s[i] == p[j + 1])
            j ++ ;
        if (j == m - 1)
        {
           //匹配成功的操作
            //printf("%d ", i - n);
            //……
            j = ne[j];//还原现场 因情况而定 可以省略 也可能是从头开始 j=0;
        }
    }
    return 0;
}
```

## 题目：

- [[2-Learning/02-算法/03-刷题理模型/串相关模型/KMP/KMP|KMP]]          [[剪布花条|剪布花条]]

- [[拓展 循环结问题(头疼警告）|拓展 循环结问题(头疼警告）]]
- [[深入 next、字符串处理(头疼）|深入 next、字符串处理(头疼）]]

之前都是把找的题都刷完才结束一块的……第一次写到心态爆炸 以后有缘再见……kmp

- [匹配统计](https://www.acwing.com/problem/content/description/162/)
- [奶牛矩阵](https://www.acwing.com/problem/content/description/161/)
- [寻找字符串](https://www.acwing.com/problem/content/description/3826/)
- [前后缀字符串](https://www.acwing.com/problem/content/description/4186/)

---
⬅️ [[AC自动机|AC自动机]] 🏠 [[00-刷题理模型]] ➡️ [[2-Learning/02-算法/03-刷题理模型/串相关模型/KMP/KMP|KMP]]