KMP算法模式计算问题

Question

这是我的代码和测试用例。我的问题是，KMP模式的值似乎永远不会增加，因为在上一次迭代中，我们检查了pattern[i] != pattern[j]，在当前的循环中，if (j == -1) or (pattern[j] == pattern[i])不可能是真的，除非j == -1。

def findPattern(pattern):

   j = -1
   next = [-1] * len(pattern)
   i = 0 # next[0] is always -1, by KMP definition

   while (i+1 < len(pattern)):
       if (j == -1) or (pattern[j] == pattern[i]):
           i += 1
           j += 1
           if pattern[i] != pattern[j]:
               next[i] = j
           else:
               next[i] = next[j]
       else:
           j = next[j]

   return next

if __name__ == "__main__":

   # print findPattern("aaaab")
   print findPattern("abaabc")

谢谢你，林

Answer 1

您已经增加了i和j，所以您实际上是在if (j == -1) or (pattern[j] == pattern[i])之后检查if (j == -1) or (pattern[j] == pattern[i])