Knuth–Morris–Pratt algorithm - get the prefix table

kmp.py

# Knuth–Morris–Pratt algorithm - get the prefix table
class KMP:
  def prefixTable(self, s):
    table = []

    table.append(0)
    j = 0
    for i in range(1,len(s)):
      if s[i] == s[j]:
        table.append(j+1)
        j += 1
      else: # does not match backward search until match or j = 0
        while j != 0:
          j = table[j-1]
          if s[j] == s[i]:
            table.append(j+1)
            j += 1
            break
        
        if j == 0:
          table.append(0)
        
      
    return table

print(KMP().prefixTable("ABABACACACABABCA"));