code: def knuth_morris_pratt(s, t):
      
      sep = '\x00'                   # special unused character
      assert sep not in t and sep not in s
      f = maximum_border_length(t + sep + s)
      n = len(t)
      for i, fi in enumerate(f):
          if fi == n:                # found a border of the length of t
              return i - 2 * n       # beginning of the border in s
      return -1
docs: Find a substring by Knuth-Morris-Pratt
  
      :param s: the haystack string
      :param t: the needle string
      :returns: index i such that s[i: i + len(t)] == t, or -1
      :complexity: O(len(s) + len(t))