#!/usr/bin/env python
# coding: utf
'''
Вычисление z-функции и ¶-функции строки
'''

import sys

def zfun(s, debug=False):
    '''Вычисление z-функции строки'''
    def dump(c):
        if not debug: return
        print c, "".join((k==l and "<" or " ")+s[k]+(k==r and ">" or " ") for k in xrange(n))
        print " ", "".join((k==i and "^{0}^" or " {0} ").format(z[k]) for k in xrange(n))
    n=len(s)
    z=[0]*n
    l=r=0
    for i in xrange(1,n):
        dump(":")
        if i <= r:
            z[i] = min (r-i+1, z[i-l])
            dump("=")
        while i+z[i] < n and s[z[i]] == s[i+z[i]]:
            z[i]+=1
            dump("+")
            # Эта проверка не зависит от цикла, её можно вынести за его пределы
            # оставлена тут только для наглядности
            if i+z[i]-1 > r:
                l, r = i, i+z[i]-1
                dump("@")
    return z

def pfun(s, debug=False):
    '''Вычисление ¶-функции строки'''
    def dump(c):
        print c,  "".join((k!=j and " {0} " or "<{0}>").format(s[k]) for k in xrange(n))
        print " ","".join(" {0} ".format(n) for n in pi)+"^ ^"
    n,pi=len(s),[0]
    for c in s[1:]:
        j=pi[-1]
        dump(":")
        while j>0 and c!=s[j]:
            j=pi[j-1]
            dump("<")
        if c==s[j]:
            j+=1
            dump("+")
        pi.append(j)
    return pi

def pfun_short(s):
    '''Вычисление ¶-функции строки (короткий вариант)'''
    n,pi=len(s),[0]
    for c in s[1:]:
        j=pi[-1]
        while j>0 and c!=s[j]: j=pi[j-1]
        if c==s[j]: j+=1
        pi.append(j)
    return pi

if len(sys.argv)>2:
    print eval(sys.argv[2]+"(sys.argv[1],True)")
else:
    print zfun(sys.argv[1])
    print pfun(sys.argv[1])