kmp.py

def ary(p):
  f = [0]
  i = 1
  j = 0
  while i < len(p):
    if p[i] == p[j]:
      f.append(j+1)
      i = i + 1
      j = j + 1
    elif j > 0:
      j = f[j-1]
    else:
      f.append(0)
      i = i + 1
  print(f)
  return f

def genTexArray(str):
  f = ary(str)
  for i in range(0, len(str)):
    print("{}&{}&{}&{}\\\\".format(i, str[1:i+1], str, f[i]))
    print("\\hline")

#Note to self: KMP works because we're logically shifting the pattern around by changing the character (index) that is being compared to the character in the text. The failure array returns the offset that we're going to set the pattern comparison index to. 

def kmp(text, pattern):
  f = ary(pattern)
  i = 0
  j = 0
  while i < len(text):
    if text[i] == pattern[j]:
      if j == len(pattern) - 1:
        return i-j
      else:
        print("Matched", text[i], "at offset i:", i, "j:",j,"continuing...")
        i = i + 1
        j = j + 1
    else:
      if j > 0:
        print("Mismatch, setting pattern offset to", f[j-1])
        j = f[j-1]
      else:
        print("Linearly searching at text index", i)
        i = i + 1
  return -1

kmp("abaxyabacabbaababacaba", "abacaba")