单模式串匹配问题与KMP算法

单模式串匹配问题

问题定义

给出一个字符串T,称为模式串,再给出一个字符串S,称为原串,问模式串在原串中是否出现,出现位置都有哪些?

举个例子,T = “ha” ,S = “hahaschool” ,T在S中出现了两次,分别是S[0~1]和S[2~3](下标从0开始)。

朴素解法

很简单,只要枚举T在S中出现位置的起点和终点,然后再逐位把S中的字符和T中对应位置的字符比对,如果全部对应,就说明T在S的该段匹配。

优化解法

在暴力匹配中,如果发生了失配(S中的字符不等于T中对应位置的字符),那么我们将会放弃当前的匹配进度,直接从S的下一位开始匹配。如果我们可以保留一部分的匹配进度,就可以减少计算量。这种想法就是我们接下来要讲的KMP算法的源头。

KMP算法

求Next数组

 

使用Next数组加速字符串匹配

 

Next数组的其他应用

最长循环节

结合动态规划

Extended KMP

Leave a Reply

Scroll to top