"""

 Author: Eugen Sawin <sawine@informatik.uni-freiburg.de>

 """

 def main():   

     args = parse_arguments()

     print "next ", next(args.pattern)

     for x in range(len(args.text)): 

         pad = ""

         for p in range(2 - len(str(x))):

             pad += " "

         print str(x) + pad,

     print

     #print " ".join([str(i) for i in range(len(args.text))]) 

     for x in range(len(args.text)): 

         pad = " "

         print args.text[x] + pad,

     #for i in range(len(args.text)):

     #    pad = ""

     #    for x in range(1, len(str(i))):

     #        pad += " "

     #    print args.text[i] + pad,

     print

     print kmp(args.text, args.pattern)

 def kmp(text, pattern):    

     l = []

     n = next(pattern)

     j = 0

     for i in range(len(text)):

         pad = ""

         for x in range(1, i-j+1):

             pad += "   "

         print pad + "  ".join(pattern[:j+1]),

         while j >= 0 and text[i] != pattern[j]:           

             j = n[j]

         j += 1

         if j == len(pattern):

             print " matched",

             l.append(i - len(pattern) + 1)

             j = n[j]

         print

     return l

 def next(pattern):

     n = [-1]

     j = -1

     for i in range(len(pattern)):        

         while j >= 0 and pattern[i] != pattern[j]:

             j = n[j]        

         j += 1

         n.append(j)        

     return n

 from argparse import ArgumentParser

 def parse_arguments():

     parser = ArgumentParser(description="KMP.")

     parser.add_argument("text", help="the text")

     parser.add_argument("pattern", help="the pattern")     

     return parser.parse_args()

 if __name__ == "__main__":

     main()