Envío 7185

Código

class SuffixArray:
    def __init__(self, T):
        self.T = T + '$'
        self.n = len(self.T)
        self.MAX_N = 201000
        self.c = [0] * self.MAX_N
        self.RA = [0] * self.MAX_N
        self.tempRA = [0] * self.MAX_N
        self.SA = [0] * self.MAX_N
        self.tempSA = [0] * self.MAX_N
        self.Phi = [0] * self.MAX_N
        self.PLCP = [0] * self.MAX_N
        self.LCP = [0] * self.MAX_N

    def counting_sort(self, k):
        maxi = max(300, self.n)
        count = [0] * maxi
        tempSA = [0] * self.n

        for i in range(self.n):
            count[self.RA[self.SA[i] + k] if self.SA[i] + k < self.n else 0] += 1
        for i in range(1, maxi):
            count[i] += count[i - 1]
        for i in range(self.n - 1, -1, -1):
            tempSA[count[self.RA[self.SA[i] + k] if self.SA[i] + k < self.n else 0] - 1] = self.SA[i]
            count[self.RA[self.SA[i] + k] if self.SA[i] + k < self.n else 0] -= 1
        for i in range(self.n):
            self.SA[i] = tempSA[i]

    def construct_SA(self):
        for i in range(self.n):
            self.RA[i] = ord(self.T[i])
            self.SA[i] = i
        k = 1
        while k < self.n:
            self.counting_sort(k)
            self.counting_sort(0)
            tempRA = [0] * self.n
            r = 0
            tempRA[self.SA[0]] = r
            for i in range(1, self.n):
                tempRA[self.SA[i]] = r if self.RA[self.SA[i]] == self.RA[self.SA[i - 1]] and \
                                           self.RA[self.SA[i] + k] == self.RA[self.SA[i - 1] + k] else r + 1
                r = tempRA[self.SA[i]]
            self.RA = tempRA[:]
            k <<= 1

    def compute_LCP(self):
        phi = [-1] * self.n
        L = 0
        for i in range(1, self.n):
            phi[self.SA[i]] = self.SA[i - 1]
            while i + L < self.n and phi[i] + L < self.n and self.T[i + L] == self.T[phi[i] + L]:
                L += 1
            self.PLCP[i] = L
            L = max(L - 1, 0)
        for i in range(1, self.n):
            self.LCP[i] = self.PLCP[self.SA[i]]

    def get_border(self):
        res = -1
        for i in range(self.n):
            if self.SA[i] == 0:
                res = i
                break
        mn = self.LCP[res]
        i = res
        while i > 0 and self.n - 1 - self.SA[i - 1] == mn:
            i -= 1
            mn = min(mn, self.LCP[i])
        if i <= 0 or self.n - 1 - self.SA[i - 1] != mn:
            return -1
        else:
            return mn

    def run(self):
        self.construct_SA()
        self.compute_LCP()
        res = self.get_border()
        if res == -1:
            print(0)
        else:
            print(res)


if __name__ == "__main__":
    T = input()
    suffix_array = SuffixArray(T)
    suffix_array.run()