写在最前面

早在大二我就想写一篇KMP的总结,主要是因为大部分blog上的文章有着各种各样的不足:有的过于冗长,有的学习曲线太陡,而《挑战》和《算法竞赛》上相关部分都因为字符串相关的内容过多,KMP算法部分不甚详尽。但是当时没有发在blog上,因为感觉从next数组谈起的话,算法的推导总会很奇怪、不顺畅。
时隔两年,花了两天时间,重新梳理了逻辑,缀字成文。

KMP算法有什么用

在文本编辑中,我们经常要在一段文本(text)中找到一串我们想要的字符串(即模板,pattern)的位置。由此,便产生了字符串的匹配问题。而KMP就是为高效解决这一问题提出来的。
kmp1

事实上,KMP算法的运行速度和理解的难度都高于其他的单文本单模板匹配算法。但是KMP算法在Tier树上扩展得到的AC自动机算法,是解决单文本多模板匹配的不二法门。如果读者有志于ACM竞赛的话,KMP算法是不能不理解的基础内容。

基础定义

这里简单地定义几个基础的名词,随着推导的深入,新的名词会在文中给出定义。

  • 文本较长,模板较短。我们在文本链上查找模板链。
  • 文本用T表示,长度为n。模板用P表示,长度为m。
  • 文本指针:一个指针
Read the rest