上一回，我们看到串的定义和基本操作，这一会，我们看到串的一个典型应用——模式匹配！
简单的模式匹配算法
子串的定位操作通常称为串的模式匹配，它求的是子串（常称模式串）在主串中的位置。下面给出一种不依赖于其他串操作的暴力匹配算法。
def index(s, t):
i, j = 1, 1
while i <= len(s) and j <= len(t):
if s[i-1] == t[j-1]:
i += 1
j += 1 # 继续比较后继字符
else:
i, j = i-j+2, 1 # 指针后退重新开始匹配
return i-len(t)if j > len(t)else 0
在上述算法中，分别用计数指针 i 和 j 指示主串 s 和模式串 t 中当前正待比较的字符位置。算法思想为：从主串 s 的第 1 个字符起，与模式 t 中的第 1 个字符比较，若相等，则继续逐个比较后续字符；否则从主串的下一个字符起，重新和模式的字符比较；以此类推，直至模式 t 中的每个字符依次和主串 s 中的一个连续的字符序列相等，则称匹配成功，函数值为与模式 t 中的第 1 个字符相等的字符在主串 s 中的序号，否则称匹配不成功，函数值为 0。下图展示了模式 t='abcac'和主串 s='ababcabcacbab'的匹配过程，每次匹配失败后，都把模式 t 后移 1 位。
暴力匹配算法的最坏时间复杂度为 O(mn)，其中 n 和 m 分别为主串和模式串的长度。
改进的模式匹配算法——KMP 算法
上图的匹配过程，在第 3 趟匹配中，i=7、j=5 的字符比较不等，于是又从 i=4、j=1 重新开始比较。然而，仔细观察会发现，i=4 和 j=1，i=5 和 j=1 及 i=6 和 j=1 这 3 次比较都是不必进行的，因为从第 3 次部分匹配结果可知，主串中第 4、5 和 6 个字符是'b'、'c' 和 'a'。因为模式中第 1 个字符是'a'，因此它无需再和这 3 个字符进行比较，而仅需将模式向右滑动 3 个字符的位置继续进行 i=7、j=2 时的字符比较即可。
在暴力匹配中，每趟匹配失败都是模式后移 1 位再从头开始比较。而某 次已匹配相等的字符序列是模式的某个前缀，这种频繁的重复比较相当于模式串在不断地进行自我比较，这就是其低效率的根源。因此，可以从分析模式本身的结构着手，如果已匹配相等的前缀序列中有某个后缀正好是模式的前缀，那么就可以将模式向右滑动到与这些字符对齐的位置，主串 i 指针无需回溯，并继续从该位置开始进行比较。而模式向右滑动的位数的计算仅与模式本身的结构有关，与主串无关（在这里理解起来会比较困难，没关系，带着这个问题继续往后看）。
字符串的前缀、后缀和部分匹配值
要了解子串的结构，首先要弄清楚几个概念：前缀、后缀和部分匹配值。前缀指除最后一个字符以外，字符串的所有头部子串；后缀指除第 1 个字符外，字符串的所有尾部子串；部分匹配值则为字符串的前缀和后缀的最长相等前后缀长度。下面以'ababa'为例进行说明：
- 'a'的前缀和后缀都是空集合，最长相等前后缀长度为 0。
- 'ab'的前缀为{a}，后缀为{b}，{a}∩{b}=∅，最长相等前后缀长度为 0。
- 'aba'的前缀为{a,ab}，后缀为{a,ba}，{a,ab}∩{a,ba}={a}，最长相等前后缀长度为 1。
- 'abab'前缀{a,ab,aba}∩后缀{b,ab,bab}={ab}，最长相等前后缀长度为 2。
- 'ababa'前缀{a,ab,aba,abab}∩后缀{a,ba,aba,baba}={a,aba}，公共元素有 2 个，最长相等前后缀长度为 3。
故字符串'ababa'的部分匹配值为 0 0 1 2 3。
这个部分匹配值有什么作用呢？
回到最初的问题，主串为 a b a b c a b c a c b a b，子串为 a b c a c。
利用上述方法容易写出子串'abcac'的部分匹配值为 0 0 0 1 0，将部分匹配值写成数组形式，就得到了部分匹配值（Partial Match，PM）的表。
编号 | 1 | 2 | 3 | 4 | 5 |
s | a | b | c | a | c |
PM | 0 | 0 | 0 | 1 | 0 |
下面用 PM 表来进行字符串匹配：
主串 | a | b | a | b | c | a | b | c | a | c | b | a | b |
子串 | a | b | c |
第 1 趟匹配过程：
发现 c 与 a 不匹配，前面的 2 个字符'ab' 是匹配的，查表可知，最后一个字符 b 对应的部分匹配值为 0，因此按照下面的公式算出子串需要向后移动的位数：
移动位数=已匹配的字符数-对应的部分匹配值
因为 2-0=2，所以将子串向后移动 2 位，如下进行第 2 次匹配：
主串 | a | b | a | b | c | a | b | c | a | c | b | a | b |
子串 | a | b | c | a | c |
第 2 趟匹配过程：
发现 c 与 b 不匹配，前面 4 个字符'abca'是匹配的，最后一个字符 a 对应的部分匹配值为 1，4-1=3，将子串向后移动 3 位，如下进行第 3 次匹配：
主串 | a | b | a | b | c | a | b | c | a | c | b | a | b |
子串 | a | b | c | a | c |
第 3 趟匹配过程：
子串全部比较完成，匹配成功。整个匹配过程中，主串始终没有回退，故 KMP 算法可以在 O(m+n)的时间数量级上完成串的模式匹配操作，大大提高了匹配效率。
某次发生失配时，如果对应的部分匹配值为 0，即已匹配相等序列中没有相等的前后缀，此时移动的位数最大，直接将子串首字符右移到主串 i 位置进行下一趟比较；如果已匹配相等序列中存在最大相等前后缀（可理解为首尾重合），那么将子串向右滑动到和该相等前后缀对齐（这部分字符下一次显然不需要比较），然后再从主串 i 位置进行下一趟比较。
KMP 算法的原理是什么？
我们刚刚学会了怎样计算字符串的部分匹配值、怎样利用子串的部分匹配值快速的进行字符串匹配操作，但公式“移动位数=已匹配的字符数-对应的部分匹配值”的意义是什么呢？
如表 1 所示，当 c 与 b 不匹配时，已匹配 'abca' 的前缀 a 和后缀 a 为最长公共元素。已知前缀 a 与 b、c 均不同，与后缀 a 相同，故无须比较，直接将子串移动“已匹配的字符数-对应的部分匹配值”，用子串前缀后面的元素与主串匹配失败的元素开始比较即可，如表 2 所示。
表 1：失配后移动情况
主串 | a | b | a | b | c | a | b | c | a | c | b | a | b |
a | b | c | a | c | |||||||||
a | b | c | a | c | |||||||||
a | b | c | a | c | |||||||||
a | b | c | a | c |
表 2：直接移动到合适的位置
主串 | a | b | a | b | c | a | b | c | a | c | b | a | b |
a | b | c | a | c | |||||||||
a | b | c | a | c |
对算法的改进方法：
已知：移动位数=已匹配的字符数-对应的部分匹配值。
写成：Move=(j-1)-PM[j-1]。
使用部分匹配值时，每当匹配失败，就去找它前一个元素的部分匹配值，这样使用起来有些不方便，所以将 PM 表右移 1 位，这样哪个元素匹配失败，直接看它自己的部分匹配值即可。
将上例中的字符串'abcac'的 PM 表右移 1 位，就得到了 next 数组：
编号 | 1 | 2 | 3 | 4 | 5 |
s | a | b | c | a | c |
next | -1 | 0 | 0 | 0 | 1 |
我们注意到：
- 第 1 个元素右移以后的空缺用 -1 来填充，因为若是第 1 个元素匹配失败，则需要将子串向右移动 1 位，而不需要计算子串移动的位数。
- 最后一个元素在右移过程中溢出，因为原来的子串中，最后一个元素的部分匹配值是其下一个元素使用的，但显然已没有下一个元素，故可以舍去。
这样，上式就改写为：
Move=(j-1)-next[j]
相当于将子串的比较指针 j 回退到
j=j-Move=j-((j-1)-next[j])=next[j]+1
有时为了使公式更加简洁、计算简单，将 next 数组整体+1。
因此上述子串的 next 数组也可以写成
编号 | 1 | 2 | 3 | 4 | 5 |
s | a | b | c | a | c |
next | 0 | 1 | 1 | 1 | 2 |
最终得到子串指针变化公式 j=next[j]。在实际匹配过程中，子串在内存里是不会移动的，而是指针在变化。next[j]的含义是：在子串的第 j 个字符与主串发生失配时，则跳到子串的 next[j]位置重新与主串当前位置进行比较。
如何推理 next 数组的一般公式？设主串为
模式串为
当主串中第 i 个字符与模式串中第 j 个字符失配时，子串应向右滑动多远，然后与模式中的哪个字符比较？
假设此时应与模式中的第 k（k<j）个字符继续比较，则模式中前 k-1 个字符的子串必须满足下列条件（不存在 k'>k）：
若存在满足上述条件的子串，则发生失配时，仅需将模式向右滑动至模式中第 k 个字符和主串的第 i 个字符对齐，此时模式中前 k-1 个字符的子串必定与主串中第 i 个字符之前长度为 k-1 的子串相等，由此，只需从模式第 k 个字符与主串第 i 个字符继续比较即可，如图所示。
当模式串已匹配相等字符序列中不存在满足上述条件的子串时（可以看成 k=1），显然应该将字符串右移 j-1 位，让主串第 i 个字符和模式第 1 个字符进行比较，此时右移位数最大。
当模式串第 1 个字符（j=1）与主串第 i 个字符发生失配时，规定 next[1]=0（可理解为将主串第 i 个字符和模式串第 1 个字符的前面空位置对齐，也即模式串右移 1 位。）。将模式串右移 1 位，从主串的下一个位置（i+1）和模式串的第一个字符继续比较。
通过上述分析可以得出 next 函数的公式：
上述公式不难理解，手工求 next 值时，用之前的方法也很好求，但如果想用代码实现，貌似难度还真不小，我们来尝试推理求解的科学步骤。
首先有公式可知
next[1]=0
设 next[j]=k，此时 k 应满足的条件在上文中已描述。
此时 next[j+1]=？可能有 2 种情况：
- 若 p[k]=p[j]，则表明在模式串中'p[1]...p[k-1]p[k]'='p[j-k+1]...p[j-1]p[j]'并且不存在 k'>k 满足上述条件。此时 next[j+1]=k+1，即 next[j+1]=next[j]+1。
- 若p[k]≠p[j]，则表明在模式串中'p[1]...p[k-1]p[k]'≠'p[j-k+1]...p[j-1]p[j]'。
此时可以把求 next 函数值的问题视为一个模式匹配问题。用前缀
去跟后缀
匹配，则当
时应将
向右滑动至第 next[k]个字符和
比较，如果
与
还是不匹配，那么需要寻找长度更短的相等前后缀，下一步继续用
与
比较，以此类推，直到找到某个更小的 k'=next[next...[k]]（1<k'<k<j），满足条件
则 next[j+1]=k'+1。
也可能不存在任何 k'满足上述条件，即不存在长度更短的相等前缀后缀，令 next[j+1]=1。理解起来有一点费劲？下面举一个简单的例子。
求模式串的 next 值
j | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
模式 | a | b | a | a | b | c | a | b | a |
next[j] | 0 | 1 | 1 | 2 | 2 | 3 | ？ | ？ | ？ |
表的模式串中以求得 6 个字符的 next 值，现在求 next[7]，因为 next[6]=3，又
则需比较
和
（因 next[3]=1），由于
而 next[1]=0，所以 next[7]=1；求 next[8]，因
则 next[8]=next[7]+1=2；求 next[9]，因
则 next[9]=3。
通过上述分析写出求 next 值的程序如下：
def get_next(t):
i, j, nex = 1, 0, [0]*len(t)
while i < len(t):
if j == 0 or t[i-1] == t[j-1]:
i += 1
j += 1
nex[i-1] = j # 若 p[i]=p[j]，则 next[j+1]=next[j]+1
else:
j = nex[j-1] # 否则令 j=next[j]，循环继续
return nex
计算机执行起来效率很高，但对于手工计算来说会很困难。因此，当需要手工计算时，依然还是用最初的方法。
与 next 数组的求解相比，KMP 的匹配算法相对要简单很多，它在形式上与简单的模式匹配算法很相似。不同之处仅在于当匹配过程产生失配时，指针 i 不变，指针 j 退回到 next[j]的位置并重新进行比较，并且当指针 j 为 0 时，指针 i 和 j 同时加 1。即若主串的第 i 个位置和模式串的第 1 个字符不等，则应从主串第 i+1 个位置开始匹配，具体代码如下：
def index_kmp(s, t, nex):
i, j = 1, 1
while i <= len(s) and j <= len(t):
if j == 0 or s[i-1] == t[j-1]:
i += 1
j += 1 # 继续比较后继字符
else:
j = nex[j-1] # 模式串向右移动
if j > len(t):
return i-len(t) # 匹配成功
else:
return 0
尽管普通模式匹配的时间复杂度是 O(mn)，KMP 算法的时间复杂度是 O(m+n)，但在一般情况下，普通模式匹配算法的实际执行时间近似于 O(m+n)，因此至今仍被采用。KMP 算法仅在主串与子串有很多“部分匹配”时才显得比普通算法快得多，其主要优点是主串不回溯。
KMP 算法的进一步优化
前面定义的 next 数组在某些情况下尚有缺陷，还可以进一步优化。如表所示，模式'aaab'在和主串'aaabaaaaab'进行匹配时：
KMP 算法进一步优化示例
主串 | a | a | a | b | a | a | a | a | a | b |
模式 | a | a | a | a | b | |||||
j | 1 | 2 | 3 | 4 | 5 | |||||
next[j] | 0 | 1 | 2 | 3 | 4 | |||||
nextval[j] | 0 | 0 | 0 | 0 | 4 |
当 i=4、j=4 时，
跟
（b≠a）失配，如果用之前的 next 数组还需进行
与
、
与
、
与
这 3 次比较。事实上，因为
、
、
显然后面 3 次用一个和
相同的字符跟
比较毫无意义，必然失配。那么问题出在哪里呢？
问题在于不应该出现
理由是：当
时，下次必然是
跟
比较，如果
那么相当于拿一个和
相等的字符跟
比较，这必然导致继续失配，这样的比较毫无意义。那么如果出现了
应该如何处理呢？
如果出现了，则需要再次递归，将 next[j]修正为 next[next[j]]，直至两者不相等为止，更新后的数组命名为 nextval。计算 next 数组修正值的算法如下，此时匹配算法不变。
def get_nextval(t):
i, j, nextval = 1, 0, [0]*len(t)
while i < len(t):
if j == 0 or t[i-1] == t[j-1]:
i += 1
j += 1
if t[i-1] != t[j-1]:
nextval[i-1] = j
else:
nextval[i-1] = nextval[j-1]
else:
j = nextval[j-1]
return nextval
KMP 算法对于初学者来说可能不太容易理解，可以尝试多读几遍本文的内容，并参考一些其他资料的相关内容来巩固这个。
因为考研复试已经尘埃落定（已被拟录取），数据结构系列暂时停止更新！后期会随便更新一些东西！
