浅谈Python描述数据结构之KMP篇

前言

"color: #ff0000">1. BF算法

"application/x-tex">Bruce-ForceBruce"application/x-tex">S=ABACABABS=ABACABAB，模式串$$T=ABABT=ABABT=ABAB，每趟匹配失败后，主串S指针回溯，模式串指针回到头部，然后再次匹配，过程如下：

def BF(substrS, substrT):
  if len(substrT) > len(substrS):
    return -1
  j = 0
  t = 0
  while j < len(substrS) and t < len(substrT):
    if substrT[t] == substrS[j]:
      j += 1
      t += 1
    else:
      j = j - t + 1
      t = 0
  if t == len(substrT):
    return j - t
  else:
    return -1

2. KMP算法

"normal">.E.Knuth、J.H.Morris、V.R.PrattD.E.Knuth、J.H.Morris、V.R.PrattD.E.Knuth、J.H.Morris、V.R.Pratt同时发现的，又被称为克努特-莫里斯-普拉特算法。该算法的基本思路就是在匹配失败后，无需回到主串和模式串最近一次开始比较的位置，而是在不改变主串已经匹配到的位置的前提下，根据已经匹配的部分字符，从模式串的某一位置开始继续进行串的模式匹配。

"normal">"ABA""ABA""ABA"，其前缀与后缀都是$$"A""A""A"，这个时候我们就不需要执行第二次匹配了，因为第一次就已经匹配过了，所以可以跳过第二次匹配，直接进行第三次匹配，即前缀位置移到后缀位置，主串指针无需回溯，并继续从该位开始比较。

"false">(Partial(Partial(Partial $$Match,PM)Match,PM)Match,PM)：字符串的前缀和后缀的最长相等前后缀长度。
"normal">′a′'a'′a′的前缀和后缀都为空集，则最长公共前后缀长度为0；$$′ab′'ab'′ab′的前缀为$${a}\{a\}{a}，后缀为$${b}\{b\}{b}，则最长公共前后缀为空集，其长度长度为0；$$′aba′'aba'′aba′的前缀为$${a,ab}\{a,ab\}{a,ab}，后缀为$${a,ba}\{a,ba\}{a,ba}，则最长公共前后缀为$${a}\{a\}{a}，其长度长度为1；$$′abab′'abab'′abab′的前缀为$${a,ab,aba}\{a,ab,aba\}{a,ab,aba}，后缀为$${b,ab,bab}\{b,ab,bab\}{b,ab,bab}，则最长公共前后缀为$${ab}\{ab\}{ab}，其长度长度为2。
"text-align: center">"text-align: left">"text-align: center">"text-align: left">"normal">"A""A""A"，即最长公共前后缀为空集，其长度为0，则下次匹配时将模式串1号位与主串的当前位进行比较。next[1]=0

"normal">"AB""AB""AB"，即最长公共前后缀为空集，其长度为0，则下次匹配时将模式串1号位与主串的当前位进行比较。next[2]=0

"text-align: left">"normal">"ABA""ABA""ABA"，即最长公共前后缀为$$"A""A""A"，其长度为1，则下次匹配时将前缀位置移到后缀位置，即模式串2号位与主串的当前位进行比较。next[3]=1

"normal">"ABAA""ABAA""ABAA"，即最长公共前后缀为$$"A""A""A"，其长度为1，则下次匹配时将前缀位置移到后缀位置，即模式串2号位与主串的当前位进行比较。next[4]=1

"normal">"ABAAB""ABAAB""ABAAB"，即最长公共前后缀为$$"AB""AB""AB"，其长度为2，则下次匹配时将前缀位置移到后缀位置，即模式串3号位与主串的当前位进行比较。next[5]=2

"normal">"ABAABC""ABAABC""ABAABC"，即最长公共前后缀为空集，其长度为0，则下次匹配时将模式串1号位与主串的当前位进行比较。next[6]=0

"text-align: left">如果模式串8号位与主串当前位不匹配，找最长公共前后缀，指针前面的子串为$$"ABAABCA""ABAABCA""ABAABCA"，即最长公共前后缀为$$"A""A""A"，其长度为1，则下次匹配时将模式串2号位与主串的当前位进行比较。next[7]=1

"text-align: left"> 位编号 1 2 3 4 5 6 7 8 索引 0 1 2 3 4 5 6 7 模式串 A B A A B C A C next -1 0 0 1 1 2 0 1

"text-align: center">"text-align: left">"application/x-tex">T_j=T_tTj"false">[j+1]=t+1=next[j]+1next[j+1]=t+1=next[j]+1next[j+1]=t+1=next[j]+1。这个时候$$j=4,t=1j=4,t=1j=4,t=1(索引)；

"normal">≠TtT_j \neq T_tTj"application/x-tex">tt位置与主串(并不是真正的主串)不匹配，则将下面的那个模式串移动到$$next[t]next[t]next[t]位置进行比较，即$$t=next[t]t=next[t]t=next[t]，直到$$Tj=TtT_j=T_tTj"application/x-tex">t=-1t="application/x-tex">t=-1t="false">[j+1]=0next[j+1]=0next[j+1]=0。这里就是$$t=next[2]=0t=next[2]=0t=next[2]=0，即下次匹配时，模式串的第1位与主串当前位进行比较。

"htmlcode">

def getNext(substrT):
  next_list = [-1 for i in range(len(substrT))]
  j = 0
  t = -1
  while j < len(substrT) - 1:
    if t == -1 or substrT[j] == substrT[t]:
      j += 1
      t += 1
      # Tj=Tt, 则可以到的next[j+1]=t+1
      next_list[j] = t
    else:
      # Tj!=Tt, 模式串T索引为t的字符与当前位进行匹配
      t = next_list[t]
  return next_list


def KMP(substrS, substrT, next_list):
  count = 0
  j = 0
  t = 0
  while j < len(substrS) and t < len(substrT):
    if substrS[j] == substrT[t] or t == -1:
      # t == -1目的就是第一位匹配失败时
      # 主串位置加1, 匹配串回到第一个位置(索引为0)
      # 匹配成功, 主串和模式串指针都后移一位
      j += 1
      t += 1
    else:
      # 匹配失败, 模式串索引为t的字符与当前位进行比较
      count += 1
      t = next_list[t]
  if t == len(substrT):
    # 这里返回的是索引
    return j - t, count+1
  else:
    return -1, count+1

3. KMP算法优化版

"application/x-tex">S=AAABAAAABS=AAABAAAAB，模式串$$T=AAAABT=AAAABT=AAAAB，按照KMP算法，匹配过程如下：

"text-align: left">"application/x-tex">SS的4号位为模式串$$TTT的4号位就已经比较了，且$$T3≠S3T_3 \neq S_3T3"application/x-tex">TT的4号位与其1、2、3号位的字符一样，即$$T3=T2=T1=T0≠S3T_3=T_2=T_1=T_0 \neq S_3T3"text-align: left">"normal">≠SjT_j \neq S_jTj"false">[j]T_{next[j]}Tnext[j]"application/x-tex">S_jSj"false">[j]=TjT_{next[j]} = T_jTnext[j]"application/x-tex">T_jTj"application/x-tex">S_jSj"false">[j]next[j]next[j]的值直接赋值为-1，即遇到这种情况，主串与模式串都从下一位开始比较。

"false">[j]=TjT_{next[j]} = T_jTnext[j]"false">[\Big[[next[j]$$]\Big]]，直至两者不相等为止(相当于了迭代)。在代码里面实现就是，如果某个字符已经相等或者第一个next[j]数组值为-1(即$$t="application/x-tex">t=-1t="htmlcode">

def getNextval(substrT):
  nextval_list = [-1 for i in range(len(substrT))]
  j = 0
  t = -1
  while j < len(substrT) - 1:
    if t == -1 or substrT[j] == substrT[t]:
      j += 1
      t += 1
      if substrT[j] != substrT[t]:
        # Tj=Tt, 但T(j+1)!=T(t+1), 这个就和next数组计算时是一样的
        # 可以得到nextval[j+1]=t+1
        nextval_list[j] = t
      else:
        # Tj=Tt, 且T(j+1)==T(t+1), 这个就是next数组需要更新的
        # nextval[j+1]=上一次的nextval_list[t]
        nextval_list[j] = nextval_list[t]
    else:
      # 匹配失败, 模式串索引为t的字符与当前位进行比较
      t = nextval_list[t]
  return nextval_list

"htmlcode">

if __name__ == '__main__':
  S1 = 'ABACABAB'
  T1 = 'ABAB'
  S2 = 'AAABAAAAB'
  T2 = 'AAAAB'

  print('*' * 50)
  print('主串S={0}与模式串T={1}进行匹配'.format(S1, T1))

  print('{:*^25}'.format('KMP'))
  next_list1 = getNext(T1)
  print('next数组为: {}'.format(next_list1))
  index1_1, count1_1 = KMP(S1, T1, next_list1)
  print('匹配到的位置(索引): {}, 匹配次数: {}'.format(index1_1, count1_1))

  print('{:*^25}'.format('KMP优化版'))
  nextval_list1 = getNextval(T1)
  print('nextval数组为: {}'.format(nextval_list1))
  index1_2, count1_2 = KMP(S1, T1, nextval_list1)
  print('匹配到的位置(索引): {}, 匹配次数: {}'.format(index1_2, count1_2))

  print('')
  print('*' * 50)
  print('主串S={0}与模式串T={1}进行匹配'.format(S2, T2))

  print('{:*^25}'.format('KMP'))
  next_list2 = getNext(T2)
  print('next数组为: {}'.format(next_list2))
  index2_1, count2_1 = KMP(S2, T2, next_list2)
  print('匹配到的位置(索引): {}, 匹配次数: {}'.format(index2_1, count2_1))

  print('{:*^25}'.format('KMP优化版'))
  nextval_list2 = getNextval(T2)
  print('nextval数组为: {}'.format(nextval_list2))
  index2_2, count2_2 = KMP(S2, T2, nextval_list2)
  print('匹配到的位置(索引): {}, 匹配次数: {}'.format(index2_2, count2_2))

"text-align: center">

"application/x-tex">S=ABACABABS=ABACABAB与模式串$$T=ABABT=ABABT=ABAB匹配时需要4次，主串$$S=AAABAAAABS=AAABAAAABS=AAABAAAAB与模式串$$T=AAAABT=AAAABT=AAAAB匹配时需要5次；修正next数组后，主串$$S=ABACABABS=ABACABABS=ABACABAB与模式串$$T=ABABT=ABABT=ABAB匹配时需要3次，主串$$S=AAABAAAABS=AAABAAAABS=AAABAAAAB与模式串$$T=AAAABT=AAAABT=AAAAB匹配时仅需要2次。

结束语

  在写本篇博客之前也是反复看参考书、视频，边画图边去理解它，这篇博客也是反复修改了好几次，最终算是把KMP解决掉了，有关字符串知识的复习也算是基本结束，下面就是刷题了(虽然在LeetCode做过了几道题)。