本文主要是介绍暑假acwing算法总结7: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写于南宁
这篇关于暑假acwing算法总结7:KMP算法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!