KMP 算法模版

正文索引 [隐藏]

给你一个模式串 T 与一个目标串 S,我们要快速找到 T 在 S 中的所有出现,复杂度为 O(|S| + |T|)

需要额外说明的是这里的代码对于 Next 数组多算了一位,相当于给原本的模式串 T 后增加了一个无法匹配的字符。在匹配的过程中一旦要比较模式串无法匹配的字符,那么就说明匹配成功了,然后本次比较一定失配,跳 Next 数组。

C++ 代码

C++ 的代码封装在一个 NameSpace 中。build 函数可以计算出模式串 pattern 的 Next 数组;match 函数求出 pattern 在 text 中的所有出现位置,并返回那些开始位置。

Python 代码

Python 代码封装在一个类中,调用构造函数传入模式串 T,初始化模式串 T 的 Next 数组。传入目标串 S 调用类的 match 函数,可以返回模式串 T 的在目标串 S 中的所有出现的开始位置。