//注:文章是蒟蒻XZY一个字一个字地码出来的,图也是一笔一笔画出来的,要转载一定要说明出处(http://k-xzy.cf)啊/(ㄒoㄒ)/~~!

1. 一些废话

首先说明,本文中的指针都不是真正的指针,指的是数组下标的编号。

KMP算法是一种改进的字符串匹配算法,由D.E.Knuth,J.H.Morris和V.R.Pratt同时发现,因此人们称它为克努特——莫里斯——普拉特操作(简称KMP算法)。KMP算法的关键是利用匹配失败后的信息,尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是实现一个next()函数,函数本身包含了模式串的局部匹配信息。时间复杂度O(m+n)。
——度娘

其实这算法简称叫做看毛片算法

2. 基本思想

问题:从字符串sup(长度为n)中找到字符串sub(长度为m)。
朴素算法:枚举字符串sub的第一个字符对应的sup中的字符的编号,再挨个比较。复杂度$O(n×m)$

kmp算法:其他都与朴素算法相同,但是它改进了“枚举字符串sub的第一个字符对应的sup中的字符的编号”这一过程,从而减小了复杂度。复杂度为$O(n+m)$

那么kmp的基本思想到底是什么呢?
如图,我们要匹配字符串sup、sub(在字符串sup里找sub),其中绿色的表示这段区域里面的字符都相等(匹配成功),红色表示那个位置的字符不同:
http://k-xzy.cf/wp-content/uploads/2017/05/kmp_1.png
如果按照朴素的做法,这时候我们就应该把sub向右移动一位,再从头判断。
但我们kmp不会这样。它是怎么做的呢?
如图,加入这两块深色区域内的字符串相同:
http://k-xzy.cf/wp-content/uploads/2017/05/kmp_2.png
http://k-xzy.cf/wp-content/uploads/2017/05/kmp_3.png
http://k-xzy.cf/wp-content/uploads/2017/05/kmp_4.png

也就是我们把sub一次移动了k位,比原来移动一位快得多。
而且省去了再次判断深色区域是否相同的复杂度。

3. 具体实现

移动字符串很简单:移动字符串其实就是移动指针。
那么我们怎么得到深色区域呢?
预处理
设$next[i]$表示在sub中,区间$[0,i]$的最长的公共前缀后缀的长度(字符串的第一位下标为0)。
什么是最长的公共前缀后缀的长度
首先,前缀就是字符串的一个子串,子串的第一位是原字符串的第一位。
如原字符串为abcdabcd,那它的前缀有:a,ab,abc,abcd,abcda,abcdab,abcdabc,abcdabcd。
后缀则反之。如原字符串依然为abcdabcd,那么它的后缀有:d,cd,bcd,abcd,dabcd,cdabcd,bcdabcd,abcdabcd。

理解了这个,我们就能理解什么是最长的公共前缀后缀了。
它是一个字符串的前缀,同时也是该字符串的后缀。但它不能使字符串本身。
如abcdabcd中,最长的公共前缀后缀就是abcd。
那它的最长的公共前缀后缀的长度就为4。

所以,对于字符串abcdabcd,它的$next$数组是这样的:
$next[0]=0,next[1]=0,next[2]=0,next[3]=0,next[4]=1,next[5]=2,next[6]=3,next[7]=4$

所以当匹配到sub的第i为不同时,此时深色区域的长度就是$next[i]$。

怎么得到next数组呢?
http://k-xzy.cf/wp-content/uploads/2017/05/kmp_5.png
(图是网上找来的,出自:http://blog.csdn.net/yutianzuijin/article/details/11954939/
如图。假设我们现在已经求得next[0]、next[1]、……next[i-1],分别表示长度为1到i的字符串的前缀和后缀最大公共长度,现在要求next[i]。由上图我们可以看到,如果位置i和位置next[i-1]处的两个字符相同,那么next[i]=next[i-1]+1。如果两个位置的字符不相同,我们可以将长度为next[i-1]的字符串继续分割,获得其最大公共长度next[next[i-1]],然后再和位置i的字符比较。这是因为长度为next[i-1]前缀和后缀都可以分割成上部的构造,如果位置next[next[i-1]]和位置i的字符相同,则next[i]=next[next[i-1]]+1。如果不相等,就可以继续分割长度为next[next[i-1]]的字符串,直到字符串长度为0为止。

代码很简单,寥寥几行:

实现了这个就很简单了。
在匹配字符串时,如果发现不匹配的字符就让指向sub的指针j改变为next[j-1],直到j为0或者位置j的字符串匹配了。
为什么是j=next[j-1]呢?回到上面的图中,当前不匹配位(红色)的编号为j,所以深色的区域的长度为next[j-1]。

至于结束匹配:当指向sup的指针i已经大于n(sup的长度)时,说明已经无法继续匹配了,匹配结束。
如果指向sub的指针j已经大于m(sub的长度)时,说明新找到了一个匹配的字符串。

具体看代码吧。
下面的代码中我没用变量n、m表示字符串长度。
supl表示字符串sup的长度,subl表示字符串sub的长度,supi表示sup的指针,subi表示sub的指针。

4. 例题&代码

都是模板题,思路我就不讲了。。。= ̄ω ̄=
1. 剪花布条 HDU - 2087
传送门= ̄ω ̄=
代码:

  1. Oulipo HDU - 1686
    传送门= ̄ω ̄=
    代码:

  1. 【模板】KMP字符串匹配 LUOGU - 3375
    传送门= ̄ω ̄=
    代码: