Write the implementation for generating pattern part, and did some testing, seems good to me. But not sure if any functional bugs? If anyone find a functional bug, appreciate for the insights.
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")
next
is the name of a builtin function in Python, and it's potentially confusing to reuse that for your own variable name, as other people will expect it to do something else - and if you need the real function at some point, it may cause problems. \$\endgroup\$ – TessellatingHeckler Oct 18 '15 at 0:57