def compute_prefix(word):
 word_length = len(word)
 prefix = ([0] * word_length)
 k = 0
 for q in range(1, word_length):
  while ((k > 0) and (word[k] != word[q])):
   k = prefix[(k - 1)]
  if (word[(k + 1)] == word[q]):
   k = (k + 1)
  prefix[q] = k
 return prefix

def compute_prefix ( word ) : word_length = len ( word ) prefix = ( [ 0 ] * word_length ) k = 0 for q in range ( 1 , word_length ) : while ( ( k > 0 ) and ( word [ k ] != word [ q ] ) ) : k = prefix [ ( k - 1 ) ] if ( word [ ( k + 1 ) ] == word [ q ] ) : k = ( k + 1 ) prefix [ q ] = k return prefix
returns the prefix of the word .