Problem: Given is a string S of length N.  Find the maximum length of a non-empty string that occurs twice or more in S as contiguous substrings without overlapping.  More formally, find the maximum positive integer len such that there exist integers l_1 and l_2 ( 1 \leq l_1, l_2 \leq N - len + 1 ) that satisfy the following:    * l_1 + len \leq l_2    * S[l_1+i] = S[l_2+i] (i = 0, 1, ..., len - 1)  If there is no such integer len, print 0.

Submission attempts (in order):

def z_algorithm(S):
    
    
    
    
    # A: 921034210
    
    

    lenS = len(S)
    A = [0] * lenS
    i = 1; j = 0
    A[0] = lenS
    
    
    while i < lenS:
        
        
        while i + j < lenS and S[j] == S[i + j]:
            j += 1
        
        if j == 0:
            i += 1
            continue

        A[i] = j

        
        # A[1] = 0, A[2] = 4 (A[0:4] == A[2:2+4] = "momo")

        
        # S[3] = S[2 + 1] = S[1] = "o" 
        
        
        

        
        
        
        
        
        
        
        
        k = 1
        while k + A[k] < j and i + k < lenS:
            A[i + k] = A[k]
            k += 1
        
        
        i += k

        
        
        
        
        
        

        #             0123456
        # S         = momomosumomomomo
        
        
        
        
        j -= k
    return A

def main():
    N = int(input())
    S = input()

    ans = 0

    
    
    
    

    for i in range(N-1):
        A = z_algorithm(S[i:])
        
        
        ans = max(ans, max(A[1:]))

    print(ans)

if __name__ == '__main__':
    main()

import random

class RollingHash(object):
    def __init__(self, S: str, MOD: int = 998244353, BASE: int = 37):
        self.S = S
        self.N = N = len(S)
        self.MOD = MOD
        self.BASE = BASE
        self.S_arr = [ord(x) for x in S]

        self.POWER = [1] * (N + 1)
        self.HASH  = [0] * (N + 1)
        p, h = 1, 0
        for i in range(N):
            self.POWER[i + 1] = p = (p * BASE) % MOD
            self.HASH[i + 1] = h = (h * BASE + self.S_arr[i]) % MOD

    def hash(self, l: int, r: int):
        # get hash for S[l:r]
        _hash = (self.HASH[r] - self.HASH[l] * self.POWER[r - l]) % self.MOD
        return _hash








def binary_search(left: int, right: int, check_func, search_max:bool=False):
    
    while abs(right - left) > 1:
        mid = (left + right) // 2
    
        if check_func(mid) ^ search_max:
            right = mid
        else:
            left = mid

    return left if search_max else right

def main():
    N = int(input())
    S = input()
    MOD = 10 ** 18 + 3
    
    BASE = random.randint(2, MOD // 2 - 1) * 2 + 1
    rs = RollingHash(S, MOD=MOD, BASE=BASE)

    D = [0] * N
    
    
    def isOK(L):
        if L == 0:
            return True
        
        for i in range(min(L, N - 2 * L + 1)):
            D[i] = rs.hash(i, i + L)
        hashes = set()
        for i in range(L, N - L + 1):
            
            hashes.add(D[i - L])
            D[i] = v = rs.hash(i, i + L)
            
            if v in hashes:
                return True
        return False

    
    
    
    ans = binary_search(0, N // 2 + 1, isOK, search_max=True)
    print(ans)

if __name__ == '__main__':
    main()

Verdicts: Wrong Answer

Accepted