KMP(1)

字符串匹配问题

 首先我们先把问题明确一下,给定两个字符串P[1..P.len]和S[1..S.len],找出P在S中第一次出现的位置L,即最小的L满足P[1..len]=S[L..L+len-1]。例如”HA”在”WAHAHA”中第一次出现的位置是3(这一节约定下标都是从1开始)

暴力算法

 从小到大枚举L,然后判断P[1..len]=S[L..L+len-1]的条件是不是满足;不满足就+1试下一个L。伪代码如下:

Match(P,S)
    For L = 1...S.len - P.len + 1
        Found = True
        For i = 1...P.len
            If P[i] ! = S[L + i - 1]
                Found = False
                Break
            If Found
                Return L
    Return -1

 用一张图来展示暴力匹配的过程:

 上图中第一行的字符串是S,第二行的字符串是P。同时第2行也是枚举L=1时的匹配过程,前5个字符abbba都匹配上了;但是第6个字符失配了。第3~5行是枚举L=2, 3, 4时的匹配过程,都是第一个字符就失配了;第6行是L=5时的匹配过程,第一个字符a匹配上了,第二个字符失配了

KMP算法

 首先我们定义一个函数:失配位置f(x)。f(x)==k表示当L=x时,失配的字符是S[k]。注意这个位置是在字符串S上的,而不是P上的。在上面的例子中,f(1)=6, f(2)=2, f(3)=3, f(4)=4, f(5)=6  KMP算法的优化思路就是,枚举L的过程中,跳过使失配位置减少的L。例如我L=1的时候已经辛辛苦苦匹配上5个字符S[1..5]了,在第6个字符失配,也就是f(1)=6。那么失配之后能不能至少从L=5开始匹配,跳过L=2..4。因为L=2..4时,f(2)f(3)f(4)都比f(1)还小。好歹f(5)等于f(1),所以从L=5开始匹配  跳过使失配位置减少的L还有一个好处,就是从L=x跳到L=y时,其实并不用从S[y]开始匹配,而是直接从S[f(x)]开始匹配即可

 在上图的例子中,L=1时,在f(1)=7失配。这时我们跳到L=4继续(为什么在L=4继续,看上面一段文字),注意继续时我们并不用再比较P[1]和S[4],P[2]和S[5], P[3]和S[6],而是直接比较P[4]和S[f(1)](S[f(1)] = S[7])

 如上图所示,如果L=x时,P[1..100]与S[x..x+99]匹配上。那么L=x+1时,P[1..99]能与S[x+1, x+99]匹配上当且仅当P[1]=P[2]=P[3]=P[4]=…=P[100],也就是P[1..100]是aaaa….a这样类型的  同理,L=x+2时,P[1..98]能与S[x+2 … x+99]匹配当且仅当P[1]=P[3]=P[5]…=P[99]且P[2]=P[4]=P[6]=…P[100],也就是P[1..100]是ababab…ababab这样类型的  再同理,L=x+3时,P能匹配到S[x+99]的位置当且仅当P[1..100]是abcabcabc…abcabc这样类型的  用更一般的话说,如果在L=x时,P[1..K]匹配上了S[x..x+K-1];那么当L=x+d时,P和S匹配的两段是P[1..K-d]匹配S[x+d .. x+K-1],而S[x+d .. x+K-1]又等于P[1+d..K](根据L=x时的匹配)。所以在P[K+1]失配时,KMP的思路是,找一个最小的d满足P[1..K-d]==P[1+d..K]  形象的说也就是找到P[1..K]的一个最长前缀,并且这个前缀同时也是P[1..K]的一个后缀,也就是P[1..K]的前j个字符组成的字符串和后j个字符组成的字符串相等  比如P[1..6]=”aaaaaa”,那么这个(同时也是后缀的)最长前缀是P[1..5]=”aaaaa”;如果P[1..6]=”abaaba”,那么这个(同时也是后缀的)最长前缀是P[1..3]=”aba”;如果P[1..6]=”ababab”,那么这个(同时也是后缀的)最长前缀是P[1..4]=”abab”……  如果我们知道P[1..K]的(同时也是后缀的)最长前缀是P[1..j],我们就记作next[K]=j。这个next数组也叫作next函数  对于一个字符串P来说,我们可以先手算出对应next数组,例如”bababb”的next=[0, 0, 1, 2, 3, 1]  有了next数组,就意味着我们可以达成KMP的优化思路:

  1. 当匹配P[1..K]与S[x..x+k-1]都成功,而P[K+1]与S[x+K]失配时
  2. 通过将P[next[K]]对准S[x+k-1],实现跳过使失配位置减少的L
  3. 继续比较P[next[K]+1]与S[x+K],而不用从P[1]开始比较

 有了next数组,KMP匹配的伪代码是这样的。注意我们特别让next[0]=-1:

j = 0
For i = 1...S.len
{
    //这时p[j]与S[i-1]是匹配上的,尝试匹配P[j+1]与S[i]
    while(j >= 0 && S[i] != P[j + 1])
        j = next[j]
    j = j + 1
    if(j == P.len)
        return i - P.len + 1
}

 用图示来展示KMP的过程(已知next数组):

 上图从第三行开始匹配,注意是P[j+1]匹配S[i],所以一开始S[1..5]匹配上P[1..5]。这时i=6,j=5开始尝试匹配S[6]和P[6],匹配失败,j = next[j]=next[5]=3  于是第4行尝试匹配S[6]和P[j+1]=P[4],成功。之后一直成功匹配到S[7]和P[5]。这时S[8]和P[6]匹配失败,j = next[j]=next[5]=3  于是第5行尝试匹配S[8]和P[4],失败。j = next[j]=next[3]=1。于是第6行尝试匹配S[8]和P[2],失败。j = next[j]=next[1]=0。于是第7行尝试匹配S[8]和P[1],失败。j = next[j]=next[0]=-1。这时j==-1会跳出while循环,j++使得j=0。然后进行下一次i=9的循环  于是第8行i=9, j = 0,尝试匹配S[9]和P[1],成功。之后一直成功匹配到S[13]和P[5]。这时S[14和S[6]匹配失败,j = next[j]=next[5]=3  于是第9行,S[14]匹配P[4]成功,S[15]匹配P[5]成功,S[16]匹配P[6]失败,j = next[j]=next[5]=3  于是第10行,S[16]匹配P[4]成功,S[17]匹配P[5]成功,S[18]匹配P[6]成功,这时找到了一个完成的匹配  假设已知next数组,KMP算法的复杂度显然就是O(i变化的总量+j变化的总量),其中i是从1~S.len,显然一共变换O(S.len)次。J会通过j=j+1变大,也会通过j=next[j]变小。不过j变大的次数与i循环次数一样都是O(S.len)次,而每次j变小最小变到-1。所以j减小的总量最多是S.len+1,也是O(S.len)

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据结构与算法

P3391 【模板】文艺平衡树(Splay)

题目背景 这是一道经典的Splay模板题——文艺平衡树。 题目描述 您需要写一种数据结构(可参考题目标题),来维护一个有序数列,其中需要提供以下操作:翻转一个区...

3937
来自专栏数据结构与算法

内存的计算

因为本人考试经常MLE,所以想总结一下与内存计算有关的内容 内存计算公式 内存=变量数量*变量类型所占的字节/1024/1024(M) 常见的变量类型所占的字节...

36110
来自专栏糊一笑

非比较排序算法总结与实现

之前一篇文章介绍了几种常用的比较排序算法,下面介绍的是几种非比较排序算法。 非比较排序算法内部引用的都是计数排序,当然你也可以将计数排序换为其他的比较排序算法。...

2958
来自专栏尾尾部落

[LeetCode] Longest Common Prefix 最长公共前缀 [LeetCode] Longest Common Prefix 最长公共前缀

链接:https://leetcode.com/problems/longest-common-prefix/#/description 难度:Easy ...

882
来自专栏数据结构与算法

Splay详解(三)

前言 上一节我们学习了splay所能解决的基本问题,这节我来讲一下splay怎么搞区间问题 实现 splay搞区间问题非常简单,比如我们要在区间l,r上搞事情,...

2667
来自专栏数据结构与算法

P2023 [AHOI2009]维护序列

老师交给小可可一个维护数列的任务,现在小可可希望你来帮他完成。 有长为N的数列,不妨设为a1,a2,…,aN 。有如下三种操作形式: (1)把数列中的一段数全部...

25310
来自专栏cs

爬虫前的准备

2966
来自专栏Bingo的深度学习杂货店

Q167 Two Sum II - Input array is sorted

Given an array of integers that is already sorted in ascending order, find two n...

2665
来自专栏小樱的经验随笔

hihoCoder #1082 : 然而沼跃鱼早就看穿了一切(字符串处理)

#1082 : 然而沼跃鱼早就看穿了一切 时间限制:1000ms 单点时限:1000ms 内存限制:256MB 描述 ? fjxmlhx每天都在被沼跃鱼刷屏,因...

2675
来自专栏WindCoder

《简明 Python 教程》学习笔记-运算符与表达式

又两天没更新了,暂且同步两篇之前的笔记。运算符与表达式这一块感觉主要就是运算符与它们的用法以及优先级了。

662

扫码关注云+社区