"""

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