Envío 7162

Código

from sys import stdin

def get_border(s, sa, lcp):
    n = len(s)
    i = sa.index(0)
    while i > 0 and (n - sa[i - 1]) != lcp[i]:
        i -= 1
    if n - sa[i - 1] == lcp[i]:
        return (i - 1, lcp[i])
    return None

def create_lcp_array(s, sa):
    n = len(s)
    phi = [-1 for _ in range(n)]

    for i in range(1, n):
        phi[sa[i]] = sa[i - 1] 

    nlcp = [0 for _ in range(n)]
    l = 0
    for i in range(n):
        p = phi[i]
        if p == -1:
            continue
        while i + l < n and p + l < n and s[i+l] == s[p+l]:
            l += 1
        nlcp[i] = l
        l = max(0, l - 1)

    lcp = [0 for _ in range(n)]
    for i in range(n):
        lcp[i] = nlcp[sa[i]]
    return lcp

def eq(e1, e2):
    return e1[0] == e2[0] and e1[1] == e2[1]

def create_suffix_array(s):
    n = len(s)
    ra = [ord(c) for c in s]
    nra = [0 for _ in range(n)] 
    l = [[0, 0, 0] for _ in range(n)]
    k = 1
    while k <= n:
        for i in range(n):
            l[i][0] = ra[i]
            l[i][1] = ra[i + k] if i + k < n else -1
            l[i][2] = i
            nra[i] = 0

        l.sort(key = lambda e: (e[0], e[1]))

        for i in range(1, n):
            nra[l[i][2]] = nra[l[i - 1][2]] if eq(l[i], l[i - 1]) else i

        k *= 2
        ra, nra = nra, ra
    return [e[2] for e in l]

def fmt(s, sa, lcp):
    print(s)
    n = len(s)
    for i, si in enumerate(sa):
        suffix = ''.join(s[si:])
        resi = '{si:{width}}'.format(width = len(str(n)), si = si)
        res = '{res:{width}}'.format(width = n, res = suffix)
        print(f"{resi} {res} {lcp[i]}")

s = next(stdin)[:-1]
sa = create_suffix_array(s)
lcp = create_lcp_array(s, sa)
res = get_border(s, sa, lcp)
#fmt(s, sa, lcp)
if res is None:
    print(0)
else:
    print(res[1])