字符串的匹配在平常的编码过程中非常常用，在编程语言中通常是调用一个内置函数就可以实现字符串的匹配，当不让使用内置的函数，而是自己编写一个函数来实现匹配的功能，应该如何来写呢？
今天介绍两个算法，朴素匹配算法，和无回溯匹配算法中的KMP算法。
朴素匹配算法
朴素匹配算法就是按照常识来，最容易理解的逐个字符匹配。
从待匹配字符串中的某个下标i开始，匹配字符串从0开始，逐个匹配。当有不匹配的字符时，重新从i+1下标开始重复上次的匹配过程。
图(1) 朴素匹配算法
下面用代码实现一下：
t表示待匹配字符串，p表示用来匹配的字符串。
表示p字符串的第i个下标的字符。
def naive_match(t, p):
"""
t 目标字符串
p 匹配字符串
"""
m, n = len(p), len(t)
i, j = 0, 0
while i < m and j < n:
if p[i] == t[j]: # 字符相同，考虑下一字符
i, j = i + 1, j + 1
else:
i, j = 0, j - i + 1 # 字符不同，查找字符串重置，目标字符串回溯
if i == m:
return j - i
return -1
朴素匹配算法非常简单，容易理解。当然，它的效率也是很低的，造成效率低的原因是在执行过程中会有回溯。当遇到p[i] != t[j]时，匹配字符串下标置0，待匹配字符串的下标回到上一次检查的下一个位置，往回退了j - i + 1个位置。
这种操作造成的效率很低。最坏的情况是，每次匹配都是到最后一个字符的时候不匹配。例如：
待匹配字符串： 0000000000001
匹配字符串： 00001
这样需要 n-m+1次比较，总的比较次数就是(n-m+1) * m，这样它的复杂度就是：O(n*m)
KMP算法
朴素算法的效率低，根源上是把每次匹配都看成的单独的事件，没有利用到之前的匹配信息。而其他改进算法就是利用了之前的匹配信息。
KMP算法的基本思想就是在匹配中不回溯。
图(2) KMP算法图解
描述KMP算法，需要借助上图。
待匹配字符串t，和匹配字符串p。
在匹配过程中，p的第i个字符在和t的第j个字符比较，这时，～
和
～
相等，匹配完成。下面要做的步骤可以分为两个：
- 当
时，继续进行下一个字符的比较。
- 当
时，这是不需要重置
p，而是找到一个位置k()，使得
～
等于
～
，继续匹配
和
，重复上面的步骤。这样待匹配字符串也不需要回溯到前面去重新匹配。
KMP算法中的关键认识是：在匹配失败时，所有的
(
)都已经匹配成功。也就是说，待匹配字符串中的
之前的i个字符，与匹配字符串中的前i个字符
。
通过上面的分析，要找到k，完全可以先不管待匹配字符串，而是研究一下匹配字符串p，通过p找到它前移的位置k。
得出一个结论：在p中，其中的每一个字符的i都会有其对应的下标k，与待匹配的字符串无关。
因此，我们可以为匹配字符串设计一个列表来存储每一个i的下标k。假设p的长度为m，用一个长度为m的列表pnext来存储，用表元素pnext[i]来表示i个元素的下标k值。
有一种特殊情况：匹配失败后，之前所做的匹配都没有用，需要从头开始匹配，用
与
比较。在这种特殊情况下可以在
pnext[i]中存入-1来表示。显然，一直为-1。
KMP主算法
当假设pnext已经获得了，KMP的算法实现为：
def kmp_match(t, p, pnext):
"""
KMP匹配，主函数
"""
i, j = 0, 0
m, n = len(p), len(t)
while i < m and j < n:
if i == -1: # -1 匹配下一队字符
i, j = i + 1, j + 1
elif p[i] == t[j]: # 相等，匹配下一对字符
i, j = i + 1, j + 1
else:
i = pnext[i] # 从pnext中拿出下一个字符应该的位置
if i == m:
return j - i
return -1
该算法的时间复杂度为O(n)，因为j的循环次数不会超过n，i = pnext[i]的次数不会超过m。
pnext的实现
最长相等前后缀
已知pnext[0]=-1，并且pnext[0]到pnext[i-1]已知的情况下，求解pnext[i]:
- 假设
pnext[i-1]=k-1，如果，则
的最长的匹配相等长度为k，记下
pnext[i]=k。 - 如果
，就将k的值设为pnext[k]，即考虑前一个保证匹配的字符串，且更短。
- 假如k的值为-1（由第二步造成，一直到不到可以匹配的字符串），那么就将pnext[i]设置为0，将i递增后继续检查。
构造方法如下：
def gen_pnext(p):
i, k, m = 0, -1, len(p)
pnext = [-1] * m
while i < m - 1:
if k == -1 or p[i] == p[k]:
i, k = i + 1, k + 1
pnext[i] = k
else:
k = pnext[k]
return pnext
举例：匹配字符串为 abbcabcaabbcaa，得到的pnext为：
[-1, 0, 0, 0, 0, 1, 2, 0, 1, 1, 2, 3, 4, 5]
pnext生成算法的改进
在pnext的生成中，对pnext[i]的设置可以有些优化。
在图(2)中，匹配失败，假设pnext[i]=k，如果发现
，那么也一定有
，所以，这种情况下pnext[i]的位置移动到pnext[k]，这一修改减少了一个比较步骤，有可能提高效率。修改后：
def gen_pnext(p):
i, k, m = 0, -1, len(p)
pnext = [-1] * m
while i < m - 1:
if k == -1 or p[i] == p[k]:
i, k = i + 1, k + 1
if p[i] == p[k]:
pnext[i] = pnext[k]
else:
pnext[i] = k
else:
k = pnext[k]
return pnext
举例：匹配字符串为 abbcabcaabbcaa，得到的pnext为：
[-1, 0, 0, 0, -1, 0, 2, -1, 1, 0, 0, 0, -1, 5]
pnext的复杂度为O(m)，所以整个KMP算法的复杂度O(m+n)，由于m小于n，可以认为复杂度为O(n)，优于朴素算法。
转载自：
https://codeeper.com/2020/05/23/tech/python/structure/str-search-and-kmp.html
网友评论