RainAir
My OI Blog
RainAir
KMP模板

题目描述

算法介绍

KMP是一种字符串匹配算法,可以求出一个字符串在另一个字符串中出现的次数。
时间复杂度为$ O(N+M) $

算法实现

算法分为预处理next数组和查询两步进行。

预处理

next数组表示从起始位置到当前位置最长的前缀和后缀的长度
那么,在处理时,我们就拿当前位置和原来匹配的最长前缀的后一位比较
如果相同,那么长度+1
也就有$next[j] = next[j-1]+1$

如果不相同,那么根据此数组的性质,显而易见,你的相等的部分只能向前找
也就是说,你的这个位置的next值会减小
也就是去原来的最长相等前缀去找

所以,我们可以得到next数组的求解方法:
每一次检查上一次最长前缀的后一个位置
如果相等则$next[j]=next[i]+1$
否则令$i=next[i-1]+1$,继续循环匹配
其实这就是自己匹配自己的过程。
这是最难理解的地方,多手算几遍就好了

查询

本算法难在于next预处理,如果你已经懂了,就很简单了
我们设定两个指针i,j,指向两个字符串。
如果$i == j $那么$ i++,j++$
如果失配,就令$i = next[i-1]+1$
是不是很简单

源代码

赞赏
知识共享许可协议
本文链接: https://blog.aor.sd.cn/archives/155
如文中无特殊声明,本文采用 CC BY-NC-SA 4.0 进行许可,转载请说明出处!
希望省选不要翻车,希望我还有脑子
https://secure.gravatar.com/avatar/97c17c68a1e55e11bb5558bc0f10cc0d?s=256&d=mm&r=g

RainAir

文章作者

一个OIer。

发表评论

textsms
account_circle
email

RainAir

KMP模板
题目描述 算法介绍 KMP是一种字符串匹配算法,可以求出一个字符串在另一个字符串中出现的次数。 时间复杂度为$ O(N+M) $ 算法实现 算法分为预处理next数组和查询两步进行。 预处理 …
扫描二维码继续阅读
2017-11-25
文章归档