算法竞赛模板 KMP
KMP算法图解:
①
首先,字符串“BBC ABCDAB ABCDABCDABDE”的第一个字符与搜索词“ABCDABD”的第一个字符,进行比较。因为B与A不匹配,所以搜索词后移一位。
②
因为B与A不匹配,搜索词再往后移。
③
就这样,直到字符串有一个字符,与搜索词的第一个字符相同为止。
④
接着比较字符串和搜索词的下一个字符,还是相同。
⑤
直到字符串有一个字符,与搜索词对应的字符不相同为止。
当空格与D不匹配时,你其实知道前面六个字符是“ABCDAB”。KMP算法的想法是,设法利用这个已知信息,不要把“搜索位置”移回已经比较过的位置,继续把它向后移,这样就提高了效率。
⑥
因为空格与C不匹配,搜索词还要继续往后移。
⑦
逐位比较,直到发现C与D不匹配。于是,继续将搜索词向后移动。
⑧
逐位比较,直到搜索词的最后一位,发现完全匹配,于是搜索完成。
详解
标号(j) | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
---|---|---|---|---|---|---|---|
模式串(ch) | A | B | C | D | A | B | D |
(1) KMP算法的核心思想
——就是回溯到存在“对称”的地方。
- 注意,这里的“对称”不是指ABCCBA,而是指例如“ABCABC”中队前队尾都分别有1个“ABC”,又例如“ABCCCCCAB”中队前队尾都分别有一个“AB”。
(2) 看图说话
从图中可以分析得出,当扫描到模式串中某一位发现不匹配,总是回溯到在这一位之前的部分模式串存在重复的地方。
- 例如图解⑤中找不到字母“D”(标号3),“D”之前串为“ABCDAB”,存在队前队尾重复“AB”(2个字符),因此退回到队首的“AB”后一位“C”(标号2)。
- 例如图解⑥中找不到字母“C”(标号2),“C”之前串为“AB”,不存在重复的(0个字符),因此退回到队首最前面(标号0)。
所以,next(j)就是当模式串第j位不匹配时即将要退回到的字母标号。
(3) next计算过程
不管第一位和第二位是什么,next(0)=-1,next(1)=0,这是固定的。
ps:模式串“ABCDABD”,下标从0开始哦!
当j=1时,模式串ch[1]=“B”,“B”之前有“A”,不存在重复(0位),所以next[1]=0;
当j=2时,模式串ch[2]=“C”,“C”之前有“AB”,不存在重复(0位),所以next[2]=0;
当j=3时,模式串ch[3]=“D”,“D”之前有“ABC”,不存在重复(0位),所以next[3]=0;
当j=4时,模式串ch[4]=“A”,“A”之前有“ABCD”,不存在重复(0位),所以next[4]=0;
当j=5时,模式串ch[5]=“B”,“B”之前有“ABCDA”,存在重复“A”(1位),所以next[5]=1;
当j=6时,模式串ch[6]=“D”,“D”之前有“ABCDAB”,存在重复“AB”(2位),所以next[6]=2;
(4) nextval对next数组的优化
观察第4位“A”,当它不匹配时,按照next[4]回溯到标号0也为字母“A”,这时再匹配“A”是徒劳的,因为已知“A”不匹配,所以就继续退回到标号0字母“A”的next[0]=-1。为了计算更加直接,就有了nextval对next数组的优化:
只看前面有重复字母的几位就可以。
首先,nextval[0]默认为-1;
当1≤j≤3时,“BCD”在此之前均无重复的字母,所以nextval[j]=next[j];
当j=4时,模式串ch[4]=“A”,next[4]=0,ch[0]=“A”=ch[4],由于“A”=“A”,所以nextval[4]=nextval[0]=-1;
当j=5时,模式串ch[5]=“B”,next[5]=1,ch[1]=“B”=ch[5],由于“B”=“B”,所以nextval[5]=nextval[1]=0;
当j=6时,模式串ch[6]=“D”,next[6]=2,ch[2]=“C”=ch[6],由于“C”≠“D”,所以nextval[6]保持原样,即nextval[6]=next[6]=2;
(5) 代码实现:
功能1:返回模式串ch在主串str中首次出现的位置,未出现输出-1
功能2:返回模式串ch在主串str中出现的次数
#include<bits/stdc++.h>
#define MAX 1000005
using namespace std;
char str[MAX],ch[MAX];
int next[MAX],slen,clen;
void getnext()
{
int i=,j=-;
next[]=-;
while(i<clen)
{
if(j==-||ch[i]==ch[j])
next[++i]=++j;
else j=next[j];
}
}
//返回模式串ch在主串str中首次出现的位置
//返回的位置是从0开始的
int kmp()
{
getnext();
int i=,j=;
while(i<slen&&j<clen)
{
if(j==-||str[i]==ch[j])
{
i++;
j++;
}
else j=next[j];
}
if(j==clen)
return i-clen;
else return -;
} //返回模式串ch在主串s中出现的次数
int Count()
{
int i=,j=,sum=;
if(slen==&&clen==)
{
if(str[]==ch[])
return ;
else return ;
}
getnext();
for(i=;i<slen;i++)
{
while(j>&&str[i]!=ch[j])
j=next[j];
if(str[i]==ch[j])
j++;
if(j==clen)
{
sum++;
j=next[j];
}
}
return sum;
}
int main()
{
while(cin>>str>>ch)
{
slen=strlen(str);
clen=strlen(ch);
cout<<"模式串ch在主串s中首次出现的位置是:"<<kmp()<<endl;
cout<<"模式串ch在主串s中出现的次数:"<<Count()<<endl;
}
return ;
}
最新文章
- 《jQuery知识点总结》(一)
- MA均线组合
- DWR实现后台推送消息到web页面
- [WPF]设置背景色
- UWP开源项目 LLQNotifier 页面间通信利器(移植EventBus)
- scrollTop和scrollLeft的兼容解决万全方法
- 对csv文件的操作
- [MSSQL]SQL疑难杂症实战记录-巧妙利用PARTITION分组排名递增特性解决合并连续相同数据行
- Spring源码学习-PropertyPlaceholderHelper
- HDU 5593 ZYB&#39;s Tree 树形dp
- http://www.cnblogs.com/AloneSword/p/3370462.html
- OpenJDK与JDK的区别及Ubuntu下的安装方法
- ###C中的extern-static-const关键词
- java之jvm学习笔记十三(jvm基本结构)
- js正则表达式详解及示例讲解
- SQL SERVER 的前世今生--各版本功能对比
- day5、文件乱码怎么解决
- 【bzoj1758】[Wc2010]重建计划
- Eclipse Tomcat部署web项目时出现There are no resources that can be added or removed from the server解决办法
- thinkphp5 如何使用查询事件?
热门文章
- 45-python基础-python3-字符串-常用字符串方法(三)-startswith()-endswith()
- kubernetes容器集群管理部署master节点组件
- Logback配置,error和普通日志分离
- webpack插件之html-webpack-plugin
- data-*存数据,拿出ul li中的数据
- 【记录】@Configuration注解作用 mybatis @Param作用
- linux100day(day7)--用户管理和权限管理简单介绍
- numpy 中的broadcast 机制
- 编译lineageos1
- Linux下的上传和下载yum install -y lrzsz