KMP

题目 KMP字符串

思路分析

实际上就是两次双指针

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

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

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

代码实现

#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;
}

同类题型

• 对于字符串的比对还可以用字符串哈希 字符串哈希

视频讲解

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

⬅️ 串 🏠 00-听课板子 ➡️ trie树