KMP算法 详解+模板
本文大部分摘自szy学长的ppt《string》中的KMP部分。
%%%膜拜szy大神orz
1.概述
KMP 算法是用来解决单模匹配问题的一种算法。
如果暴力的进行单模匹配，那么时间复杂度为O(nm)。
KMP 算法通过对模式串的预处理优化了复杂度。
2.求next数组
为了叙述方便，设模式串长度为n，主串长度为m。
将模式串称为s1，主串称为s2，下标从1 开始。
我们首先对模式串预处理出一个next 数组。
next[i] 表示最大的x，满足s1[1 : x - 1] 是s1[1 : i - 1] 的后缀。
这个数组记录了失配时，模式串指针移动的目标位置。
求next[i] 时，考虑维护一个位置j，初始时为next[i - 1]。
如果s1[j] = s1[i -1]，那么next[i] 显然等于j + 1。
如果s1[j] != s1[i - 1]，那么此时需要将j 向前移动到next[j] 的位置。
一直将j 移动到next[j] 的位置，直到j = 0 或s1[j] = s1[i - 1]。
此时next[i] 等于j + 1。
由于next 是最长公共前后缀，因此在j 的移动过程中一定会经过next[i] - 1 的位置。
void getnx()
{
nx[]=;
for(int i=,j=;i<=n;)
{
nx[i]=j;
while(j&&s1[j]!=s1[i])j=nx[j];
j++,i++;
}
}
3.匹配
在匹配过程中，设在主串中匹配到位置i，模式串中匹配到位置j。
首先如果s2[i] = s1[j]，当前位置匹配成功，此时可以把i 和j 同时移动到下一个位置。
否则发生失配，需要进行调整，我们将j 置为next[j]，然后继续匹配。
同样由于next 是最长公共前后缀，因此在j 的移动过程中不会跳过可能匹配的位置。
并且模式串中j 之前的部分一定可以匹配。
void kmp()
{
for(int i=,j=;i<=m;)
{
while(j&&s1[j]!=s2[i])j=nx[j];
if(j==n)
{
// 此时找到了一个能够匹配的位置
j=nx[j];
}
else j++,i++;
}
}
可以发现两部分代码有很大相似之处。
其实可以把求next 数组过程看做用模式串与自身匹配的过程。
4.时间复杂度
在求next 的过程中，j 指针每向后移动一步，i 指针就会向后移动一步。
而j 指针每延next 移动一次，就会向前移动大于等于一步。
由于i 指针会向后移动O(n) 次，因此j 指针也只会向后移动O(n) 次，因此向前同样最多移动O(n) 次。
因此求next 数组部分复杂度为O(n)。
与之类似，可以得出匹配过程的复杂度为O(m)。
因此KMP 算法的总复杂度为O(n + m)。
尾声：
总之，KMP算法是处理字符串匹配问题的一大利器。
搭配字符串上的DP可以说是......咳咳......很有趣......
（下篇高能预告）
最新文章
- 关于linux开机进入grub问题的解决方法
- 突袭HTML5之SVG 2D入门1 - SVG综述////////////////zzzzzzzz
- tab，tabCon里放很多div，点击左右滑动一个。可根据初始化清除空的tabCon。
- 浅谈JS面向对象之创建对象
- selenium实例
- 【LeetCode OJ】Interleaving String
- MemoryStream 的GetBuffer() 和 ToArray()的区别
- UML类图与类的关系详解
- Selenium2Library系列 keywords 之 _SelectElementKeywords
- SQLSERVER2008 18456错误
- Building a Space Station（kruskal,说好的数论呢）
- cocos2d-x 背景音乐播放
- Swagger+Spring MVC框架学习分享
- IIS6,IIS7中查看w3wp进程
- apache动态添加模块
- 【LeetCode】463. Island Perimeter
- 分页（将数据库中的多条数据一页一页的显示在jsp页面中）
- vue工程利用pubsub-js实现兄弟组件之间的通信
- centos6.3部署配置LVS主从
- H5 基于Web Storage 的客户端留言板