Python实现KMP算法

算法简介


next算法

注意:本文中,字符串的索引是从0开始的。
当模式串P的第0到第j个字符和主串S的第i-j到第i个字符相匹配,但是P的第j+1个字符和S的第i+1个字符失配的时候,根据KMP算法,需要根据P的第j个字符的next值,确定下次在S上开始搜索的位置(i+1-next[j])。
next值其实就是“最长公共前后缀”,求解思路如下:
假设当前字符的索引为ind,当第ind-1个字符的next值为k的时候,如果P[ind]等于P[k]时,那么当前字符的next值是k+1。否则,当前字符的next值小于等于k,如果子串 P[0]...P[j]和子串P[ind-j]...P[ind]是P[0]...P[ind]的“最长公共前后缀”,那么当前字符的next值是j+1(k>=j+1>0),如果不存在这样的“最长公共前后缀”,那么当前字符的next值是0。整个next算法中,最难理解的部分就是利用已经得到的next[0]...next[ind-1]来求P[0]···P[ind-1]这个子串中的“最长公共前后缀”:
因为P[ind]和P[k]不相等,所以先寻找P[0]...P[k-1]的“最长公共前后缀”,它的长度就是next[k-1],如果P[next[k-1]]等于P[ind],则当前字符的next值是next[k-1]+1,否则寻找P[0]...P[next[k-1]-1]的“最长公共前后缀”,它的长度就是next[next[k-1]-1],如果P[next[next[k-1]-1]]等于P[ind],则当前字符的next值是next[next[k-1]-1]+1,以此类推,一直到计算出当前字符的next值或中途的某个子串没有“最长公共前后缀”。


Python实现

  1 def get_next(p):
  2     next = [0] * len(p)
  3     for ind in range(1, len(p)):
  4         k = next[ind-1]
  5         if p[ind] == p[k]:
  6             next[ind] = k + 1
  7             continue
  8         while k:
  9             k = next[k-1]
 10             if p[k] == p[ind]:
 11                 next[ind] = k + 1
 12                 break
 13     return next
 14 
 15 def kmp(main, pattern):
 16     next = get_next(pattern)
 17     pos = 0
 18     while pos <= len(main) - len(pattern):
 19         new_pos, ind = pos, 0
 20         while ind < len(pattern):
 21             if pattern[ind] != main[new_pos]:
 22                 break
 23             new_pos = new_pos + 1
 24             ind = ind + 1
 25         if ind == len(pattern):
 26             return pos
 27         elif new_pos == pos:
 28             pos = pos + 1
 29         else:
 30             pos = new_pos - next[new_pos-pos-1]
 31     return -1
 32 
 33 if __name__ == "__main__":
 34     print(kmp("115211151", "521"))
 35 

感谢浏览tim chow的作品!

如果您喜欢,可以分享到: 更多

如果您有任何疑问或想要与tim chow进行交流

可点此给tim chow发信

如有问题,也可在下面留言: