KMP算法

思想：从需要匹配的字符串本身特征出发，比如abcdabce，显然当e不匹配时，完全可以直接后移4位实现abc的匹配。也就是说算法就只需要考虑未成功匹配的字符前面字符串的前缀和后缀的匹配程度即可。
基于此思想，首先需要遍历一下字符串本身，并且在遍历的过程中需要获取当前所访问到的字符以及其前面字符组成的字符串的前缀和后缀匹配情况。其中的遍历过程中产生匹配情况用数组字符串 - 图1表示。
设待匹配字符串用字符串 - 图2表示，其长度为字符串 - 图3，那么其字符串 - 图4数组将由以下方式获取：（利用一个循环即解决了问题！）

  1. # 起始位下标为0
  2. def getNext(s):
  3.     le = len(s)
  4.     next = np.arange(len(s))
  5.     i = 0       # 遍历s以及标记后缀
  6.     j = -1       # 标记前缀
  7.     next[0] = -1
  8.     while i < le - 1:
  9.         if j == -1 or s[i] == s[j]:
  10.             i += 1
  11.             j += 1
  12.             next[i] = j
  13.         else:
  14.             j = next[j]
  15.     return next

获取字符串 - 图5数组之后就可以进行字符串匹配了：

  1. def KMP_Index(match_s, matched_s):
  2.     len0 = len(match_s)
  3.     len1 = len(matched_s)
  4.     next = getNext(s)
  5.     i = -1
  6.     j = -1
  7.     while i < len0 and j < len1:
  8.         if i == -1 or match_s[i] == matched_s[j]:
  9.             i = i + 1
  10.             j = j + 1
  11.         else:
  12.             i = next[i]
  13.     if i >= len0:
  14.         return j - len0
  15.     else:
  16.         return 0 # 没有找到

由于之前的字符串 - 图6数组获取完全没有考虑当前未被正确匹配的字符，所以在很多时候回溯产生移动之后在当前字符上面仍旧无法匹配的情况，对于以上问题进行改进：将未匹配字符考虑其中。

  1. # 起始位下标为0
  2. def getNext(s):
  3.     le = len(s)
  4.     next = np.arange(len(s))
  5.     i = 0       # 遍历s以及标记后缀
  6.     j = -1       # 标记前缀
  7.     next[0] = -1
  8.     while i < le - 1:
  9.         if j == -1 or s[i] == s[j]:
  10.             i += 1
  11.             j += 1
  12.             # 对比回溯值是否相等
  13.             if s[i] != s[j]:
  14.                 next[i] = j
  15.             # 由于当前字符回溯之后仍旧和此字符相等，继续回溯
  16.             else:
  17.                 next[i] = next[j]
  18.         else:
  19.             # 继续回溯也可以放到这里，但是这样会造成很大多余的计算量（循环回溯）
  20.             j = next[j]
  21.     return next