暑假acwing算法总结7:KMP算法
2021/7/9 20:17:24
本文主要是介绍暑假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写于南宁
这篇关于暑假acwing算法总结7:KMP算法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-10-04el-table 开启定时器下,表格的选中状态会消失是什么原因-icode9专业技术文章分享
- 2024-10-03如何安装和初始化飞牛私有云 fnOS?-icode9专业技术文章分享
- 2024-10-03如何安装 App 并连接到飞牛 NAS?-icode9专业技术文章分享
- 2024-10-03如何安装飞牛 TV 并连接到影视服务器?-icode9专业技术文章分享
- 2024-10-03如何在PVE和ESXI上安装飞牛私有云 fnOS?-icode9专业技术文章分享
- 2024-10-03fnOS国产最强NAS安装系统异常情况处理-icode9专业技术文章分享
- 2024-10-03飞牛NAS如何创建存储空间?-icode9专业技术文章分享
- 2024-10-03fnOS国产最强NAS硬盘会自动休眠吗?-icode9专业技术文章分享
- 2024-10-03fnOS国产最强NAS如何安装飞牛影视和创建媒体库?-icode9专业技术文章分享
- 2024-10-03fnOS国产最强NAS如何为家人朋友开通影视账号?-icode9专业技术文章分享