Skip to content

Instantly share code, notes, and snippets.

Show Gist options
  • Save chokychou/b24351b209e158657b2dd71639e77b1b to your computer and use it in GitHub Desktop.
Save chokychou/b24351b209e158657b2dd71639e77b1b to your computer and use it in GitHub Desktop.
Python KMP algorithm
class KMP:
def partial(self, pattern):
""" Calculate partial match table: String -> [Int]"""
ret = [0]
for i in range(1, len(pattern)):
j = ret[i - 1]
while j > 0 and pattern[j] != pattern[i]:
j = ret[j - 1]
ret.append(j + 1 if pattern[j] == pattern[i] else j)
return ret
def search(self, T, P):
"""
KMP search main algorithm: String -> String -> [Int]
Return all the matching position of pattern string P in T
"""
partial, ret, j = self.partial(P), [], 0
for i in range(len(T)):
while j > 0 and T[i] != P[j]:
j = partial[j - 1]
if T[i] == P[j]: j += 1
if j == len(P):
ret.append(i - (j - 1))
j = partial[j - 1]
return ret
def test():
p1 = "aa"
t1 = "aaaaaaaa"
kmp = KMP()
assert(kmp.search(t1, p1) == [0, 1, 2, 3, 4, 5, 6])
p2 = "abc"
t2 = "abdabeabfabc"
assert(kmp.search(t2, p2) == [9])
p3 = "aab"
t3 = "aaabaacbaab"
assert(kmp.search(t3, p3) == [1, 8])
print("all test pass")
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment