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

# KMP

## 题目 [KMP字符串](https://www.acwing.com/problem/content/833/)

![[image-ea5e60ad.png]]

## 思路分析

![[image-047e85ea.png]]![[image-9314dbb5.png]]

实际上就是两次双指针

第一次是在模式串内部的双指针匹配 求next数组

第二次是在原串和模式串之间的双指针匹配 找比对的结果

优化重点就是这个next数组 将匹配不成功是要移动的模式串次数变少

## 代码实现

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

const int N=100010,M=1000010;
int ne[N];
char s[M],p[N];

int main()
{
    int n,m;
    //从1号位置开始
    cin>>n>>p+1>>m>>s+1;

    //ne数组 实际上就一个模式串内部的匹配过程
    for(int i=2,j=0;i<=n;i++)
    {
        //j还没到头 且 匹配不成功 退而求其次
        while(j && p[i]!=p[j+1])
            j=ne[j];
        //退完后如果匹配成功 往后继续走
        if(p[i]==p[j+1])
            j++;
        ne[i]=j;
    }

    //kmp 从1处开始匹配原串和模式串
    for(int i=1,j=0;i<=m;i++)
    {
        //循环 如果j没退到开头 且不匹配 就往后退
        while(j && s[i]!=p[j+1])
            j=ne[j];
        //如果退了之后匹配了 就往后走
        if(s[i]==p[j+1])
            j++;
        if(j==n)//如果j长度与模式串相等的 就匹配完成
            cout<<i-n<<" ";
    }

    return 0;
}
```

## 同类题型

- 对于字符串的比对还可以用字符串哈希 [字符串哈希](https://www.acwing.com/problem/content/843/)

## 视频讲解

📹 配套视频讲解：kmp（acwing 视频课，原网址 Trilium 导出时未保留，待回填）

---
⬅️ [[串|串]] 🏠 [[00-听课板子]] ➡️ [[2-Learning/02-算法/02-听课板子/数据结构/trie树|trie树]]