"""

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

 """

 def main():   

     args = parse_arguments()

     print "next ", next(args.pattern)

     print kmp(args.text, args.pattern)

 def kmp(text, pattern):

     l = []

     n = next(pattern)

     j = 0

     for i in range(len(text)):

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

             #print "mismatch at text %i and pattern %i" % (i, j)

             #print "new pattern %i" % (n[j],)

             j = n[j]

         j += 1

         if j == len(pattern):

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

             j = n[j]

     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()