字符串匹配

1.朴素的串匹配算法(暴力解法)

1.1 分析

设t是目标串（母串），p是模式串（待匹配串），i , j 分别指向模式串和目标串，m、n分别是模式串p和目标串t的长度。

从目标串的第0个字符，挨个进行比较，遇到不相等的字符就停止。
模式串与目标串的下一个字符进行比较，重复上一个步骤。
一个一个字符遍历目标串直到找到为止。

1.2 Python实现：

def match(t:str, p:str):  '''  t:目标串(母串)  p:模式串(要匹配的字符串)  返回与模式串在目标串中第一次出现时的下标''' m, n = len(p), len(t) # m 和 n分别是字符串 p 和 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 # j-i得到当前j的下标，+1指向目标串的下一个元素  if i == m:  return j-i             # 返回此时母串中j的下标  return -1res = match("ababcabcacbab", "abcac")  
print(res)

程序运行结果是5；

1.3 时间复杂度分析

暴力匹配最坏的情况下，每一次都进行比较，最后一趟才匹配上，共n-m+1趟，每次模式串都进行了匹配为m次，故这个算法的时间复杂度为：O(m x n)。

朴素算法（暴力匹配）的缺点：

把每次字符都看做完全独立的操作，没有利用字符串本身的特点，字符串只有有穷多个字符。
没有利用前面已经比较的字符串得到的信息。

匹配字符串的特点：

模式串不太长
目标串的每一个字符来源于一个又穷集合，不是无穷多种取值
每个串有固定的长度

2.无回溯串匹配算法(KMP算法)

KMP算法是由3个外国人最先发现的，并以他们的名字首字母命名，该算法是一个高效的串匹配算法，该算法比较难理解，但是时间复杂度大大降低。该算法主要优化了朴素算法里把模式串里的字符看做单独随机字符的做法。具体如下：

每一次比较之后，找到不同的元素
然后通过next数组找到模式串下一次匹配的字符下标
构造next数组

2.1 KMP算法主函数

例：使用KMP算法把下图中的模式串在目标串进行进行查找，返回第一次出现时的下标：

def match_KMP(t, p, gen_pnext):  """:arg  t : 目标串  p : 模式串  next : 模式串的next数组  """ i, j = 0, 0  n, m = len(t), len(p)   # m 、 n 分别是模式串 和 目标串的长度  while i < m and j < n:  if i == -1 or t[j] == p[i]:  i, j = i+1, j+1  else:  i = gen_pnext[i]  if i == m:              # 找到匹配的子字符串，返回其下标  return j-i  return -1

2.2 next数组

首先我们介绍一下前缀和后缀的概念：
给出一个字符串 abcacab 该字符串相等的最长的前缀和后缀是ab。
练习：
1.求字符串 abbcabb，该字符串相等的前后缀为abb。
2.求字符串acgcca ,该字符串相等的前后缀为 a。
通过找到相等的前后缀，我们主要用来在KMP匹配一次之后，目标串和模式串遇到不同的字符时，在该位置目标串下次匹配的模式串字符的位置。如上图所示：目标串的a字符和模式串的c字符不一致，这时候需要构造next数组找到下次模式串匹配的字符位置a,这里的计算方法是：在模式串的不同字符的前的子字符串里找到相等的最大的前后缀的下一个字符的下标作为下次模式串匹配的位置。这里 ab 字符，没有相等的前后缀，返回下标0,对应的字符是a。

第二次匹配时：遇到目标串里的字符 b 和模式串里的 c 不一致，我们找子字符串：abca 里 最长相等前后缀 为 a，则取下标1对应的 b 字符与第一次匹配失败时的目标串的 ‘b’ 字符进行匹配。

def gen_pnext(p):  i, k, m = 0, -1, len(p)  pnext = [-1] * m  while i < m-1:  if p[i] == p[k] or k == -1:  i, k = i+1, k+1  pnext[i] = k  else:  k = pnext[k]  return pnext

这里的 gen_pnext() 函数就是我们上面解释的生成 next 数组的函数。下面稍微容易理解一点。

def p_next(patttern:str):  """:arg  pattern:传入的是待匹配字符串  """ i, k = 0, -1 # i 指向 pattern 字符串， k 初值为 -1 pnext = [-1] * len(patttern) # 生成一个长度和 pattern 一致的数组，初始值都为-1  while i < len(patttern)-1:  if k == -1:  i, k = i + 1, k + 1  pnext[i] = k  elif patttern[k] == patttern[i]:  i, k = i + 1, k + 1  pnext[i] = k  else:  k = pnext[k]  # 不相等 k 的值就会一直指向 pnext[k] return pnext