暑假acwing算法总结7:KMP算法

  • KMP算法:人类精华
#include<iostream>
using namespace std;
const int N = 100010, M = 10010; //N为模式串长度,M匹配串长度
int n, m;
int ne[M]; //next[]数组,避免和头文件next冲突
char s[N], p[M];  //s为模式串, p为匹配串
int main()
{
    cin>>n>s+1>>m>>p+1;  //下标从1开始
    //求next[]数组
    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)  //满足匹配条件,打印开头下标, 从0开始
        {
            //匹配完成后的具体操作
            //如:输出以0开始的匹配子串的首字母下标
            //printf("%d ", i - m); (若从1开始,加1)
            j=ne[j];            //再次继续匹配
        }
    }
    return 0;
}
  • 求ne数组的过程我也不是太明白下面先介绍匹配过程
  • 比如 s a b c d s a b s s a b s a为s串
  • s a b s a为p串
  • 先不管ne数组怎么求
ne数组
ne[0] 0
ne[1] 0
ne[2] 0
ne[3] 0
ne[4] 1
ne[5] 2
    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)  //满足匹配条件,打印开头下标, 从0开始
        {
            //匹配完成后的具体操作
            //如:输出以0开始的匹配子串的首字母下标
            //printf("%d ", i - m); (若从1开始,加1)
            j=ne[j];            //再次继续匹配
        }
    }
  • 开始时匹配到前两个s a
  • 此时i等于3,j等于2,j=ne[2]=0;
  • 相当于再次匹配时略去p字符串的0位从一开始匹配不上的位置开始匹配i=3的位置,因为不等会一直往后走直到出现第二个s也就是s a b c d s 的最后一个s,匹配时i=6,j还是为0,再往后走,直到j=5匹配失败,此时ne[4]=1;略去前一位,匹配的时候,第10位不相等略去,从第11位与j的第二位匹配直到j==m,输出结果
  • 匹配过程完美结束

  • 下面介绍ne数组的求法
    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;
    }
  • 就是把匹配的s、p循环数组换成了p自身的循环数组,且ne数组一定是单调递增的,明显DP
  • 2021-07-09写于南宁

上一篇:KMP专题练习记录


下一篇:不同的模式匹配方法详解(暴力、KMP、Rabin-Karp算法)