"""

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