【算法】KMP算法
简介
KMP算法由 Knuth-Morris-Pratt
三位科学家提出,可用于在一个 文本串
中寻找某 模式串
存在的位置。
本算法可以有效降低在一个 文本串
中寻找某 模式串
过程的时间复杂度。(如果采取朴素的想法则复杂度是 \(O(MN)\) )
这里朴素的想法指的是枚举
文本串
的起点,然后让模式串
从第一位开始一个个地检查是否配对,如果不配对则继续枚举起点。
前置知识
真前缀
指字符串左部的任意子串(不包含自身),如 abcde
中的 a
,ab
,abc
,abcd
都是真前缀但 abcde
不是。
真后缀
指字符串右部的任意子串(不包含自身),如 abcde
中的 e
,de
,cde
,bcde
都是真后缀但 abcde
不是。
前缀函数
一个字符串中最长的、相等的真前缀与真后缀的长度, 如AABBAAA
对应的前缀函数值是 \(2\) 。
原理
注意:在分析的时候,我们规定字符串的下标从 \(1\) 开始。
开始:
我们记扫描模式串的指针为j,而扫描文本串的指针为i,假设一开始i,j都在起点,然后让它们一直下去直到完全匹配或者失配,比如:
j
ABCD
i
ABCDEFG
然后
j
ABCD
i
ABCDEFG
最后在此完成了一次匹配,类似地如果ABCD
改为ABCC
则在此失配。
j
ABCD
i
ABCDEFG
i,j运作模式如上。
KMP算法就是,当模式串和文本串失配的时候,j
指针从真后缀的末尾跳到真前缀的末尾,然后从真前缀后一位开始继续匹配。(从而起到减少配对次数,这便是KMP算法的核心原理)
结合例子解释:
模式串: \(AABBAAA\)
文本串: \(AABBAABBAAA\)
j
指针在最后一个A处失配。
j
AABBAAA
i
AABBAABBAAA
因为此时 以j为尾的前缀
所对应的前缀函数值是 \(2\) ,所以 j指针
跳到这里:
j
AABBAAA
i
AABBAABBAAA
然后从下一位开始继续配对:
j
AABBAAA
i
AABBAABBAAA
最后
j
AABBAAA
i
AABBAABBAAA
可以看出,KMP能够有效减少配对次数。
实现
我们记
模式串
为p
,文本串
为s
。
从上面的模拟中,我们发现需要预处理出一个数组(记之为next[]
),它储存模式串中前缀对应的前缀函数\(\pi()\),如对于字符串ABCABC
:
\(\pi(0)=0\) (因为什么都没有)
\(\pi(1)=0\) (A
甚至没有真前缀和真后缀)
\(\pi(2)=0\) (AB
)
\(\pi(3)=0\) (ABC
)
\(\pi(4)=1\) (ABCA
)
\(\pi(5)=2\) (ABCAB
)
\(\pi(6)=3\) (ABCABC
)
同样地,我们发现如果用暴力朴素的想法来统计复杂度是 O(N^2) 不好,于是采用类似于上面的方法,只不过模式串配对的对象是自己罢了。
可以结合代码理解,并注意举例,尝试在纸上模拟这个过程。
for(int i=2,j=0;i<=lenp;i++){
while(j && p[j+1]!=p[i]) j=next_[j]; // 如果j指向元素的下一个元素会和当前配对位置失配,则j跳回去
if(p[j+1]==p[i]) j++; //如果能够配对上,j++
next_[i]=j; //记录当前位置的前缀函数π
}
完整代码:
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
char p[N],s[N];
int next_[N];
int main(){
cin>>s+1>>p+1;
int lenp=strlen(p+1),lens=strlen(s+1);
// build next array
for(int i=2,j=0;i<=lenp;i++){
while(j && p[j+1]!=p[i]) j=next_[j]; // 如果j指向元素的下一个元素会和当前配对位置失配,则j跳回去
if(p[j+1]==p[i]) j++; //如果能够配对上,j++
next_[i]=j; //记录当前位置的前缀函数π
}
for(int i=1,j=0;i<=lens;i++){
while(j && p[j+1]!=s[i]) j=next_[j];
if(p[j+1]==s[i]) j++;
// if match
if(j==lenp){
j=next_[j];
cout<<i-lenp+1<<endl;
}
}
for(int i=1;i<=lenp;i++) cout<<next_[i]<<' ';
cout<<endl;
return 0;
}
复杂度
\(O(N+M)\)
最新文章
- ASP.NET MVC with Entity Framework and CSS一书翻译系列文章之第二章:利用模型类创建视图、控制器和数据库
- JavaScript基本数据类型和引用数据类型
- 在iframe父界面获取iframe里面的标签
- 原生js操作dom备忘
- [J2EE] 在Web如何取得相关路径
- erlang反编译
- Regex 字符是不是汉字
- Performing a full database disaster recovery with RMAN
- 使用Vitamio打造自己的Android万能播放器(1)——准备
- 如何关闭android studio开发环境自动保存
- ocp11g培训内部教材_053课堂笔记(043)_数据备份
- docker 架构
- IO流(File类,IO流的分类,字节流和字符流,转换流,缓冲流,对象序列化)
- 工作中使用case用法小结
- shell while内获取外部变量内容
- arcgis for android 读取shp文件中文乱码解决方法
- UG中STP203和STP214的区别
- PHP获取照片exif信息
- 基于Bootstrap的Asp.net Mvc 分页的实现
- JY播放器【喜马拉雅FM电脑端,附带下载功能】
热门文章
- Building a high performance JSON parser
- 。SLI,Service Level Indicator,服务等级指标,其实就是我们选择哪些指标来衡量我们的稳定性。而 SLO,Service Level Objective,服务等级目标,指的就是我们设定的稳定性目标,比如“几个 9”这样的目标。
- @functools.lru_cache()
- list里放map list 放list
- 在不同情况下connect失败和ping不通的数据分析
- C++ Primer Plus读书笔记(六)分支语句和逻辑运算符
- Python学习【第9篇】:python中的局部变量与全局变量
- P5687 网格图
- WeCenter (最新版) 前台RCE漏洞 (2020-02-22)
- Centos7安装成功后,网卡配置及更改镜像地址为国内镜像