[数据结构与算法]OJ：字符串KMP算法 Python实现

KMP算法是一种字符串匹配算法，可以在 O(n+m) 的时间复杂度内实现两个字符串的匹配。

字符串匹配：“字符串 P 是否为字符串 S 的子串？如果是，它出现在 S 的哪些位置？” 其中 S 称为主串；P 称为模式串。

教程：https://www.zhihu.com/question/21923021/answer/1032665486

输入：主串s，模式串p

输出：匹配位置列表

过程：

1. 计算next数组。

   next数组是对于模式串而言的，定义为：next[i] 表示模式串p[:i+1]中，长度为k的前缀恰等于后缀的最大的k，其中k必须小于自身长度i.

   起始条件：next[0] = 0

   计算i位置的结果时，我们首先考虑利用ptr=i-1位置的结果。在知道next[ptr]=k时，说明p[0:k] == p[i-k:i]，如果p[k] == p[i]，则next[i] = next[ptr]+1.

   如果不相等，需要重新找尽量大的j<k，满足p[0:j] == p[i-j:i]，再试图扩展。

   考虑到p[i-j:i] == p[k-j:k]，那么j=next[k-1]是符合要求的。

   重新赋值ptr = k-1, k = next[ptr]，以此法继续迭代下去即可。因为forall i, next[i] <= i，所以每次迭代ptr必然变小。ptr<0时迭代结束，next[i]的结果确定为0.

   # calculate next
   next = [0]
   for i in range(1, len(p)):
       ptr = i-1
       while ptr >= 0: 
           if p[next[ptr]] == p[i]: 
               next.append(next[ptr] + 1)
               break
           else:
               ptr = next[ptr] - 1
       else:
           next.append(0)
   

2. 根据next数组计算匹配位置。

   起始条件：主串和模式串指针都在开头。i, j = 0, 0

   匹配过程：当成功匹配s[i] == p[j]时，正常移动指针。

   当匹配失败时，如果j > 0，我们尽量利用这段历史匹配记录。记next[j-1]=k (k<j)，那么根据next数组的性质和历史匹配记录，我们可以知道：s[i-j:i] == p[0:j], p[0:k] == p[j-k:j]

   所以s[i-k:i] == p[0:k]，可以把指针j移动到k继续匹配。这样就最大化地利用了这段历史匹配记录。

   类似地，匹配成功时也要重新开始一次新的匹配。此时也可以用同样的方法，不浪费之前的匹配记录。

   # KMP
   i, j = 0, 0
   ret = []
   while i < len(s):
       if s[i] == p[j]: 
           i, j = i+1, j+1
       elif j > 0:
           j = next[j-1]
       else:
           i += 1
       if j == len(p):
           ret.append(i - len(p))
           j = next[j-1]
   

   ret数组即为所求。

KMP的变体主要是考虑到，KMP算法可以求出对于每一个位置，s的后缀与p的前缀匹配的最大长度，即对于s的每一个位置i，满足s[i-j:i] == p[0:j]的最大的j. 有一些任务可以基于这个性质解决。

例题：LeetCode 214 Shortest Palindrome