'''
keys: 
Solutions:
Similar: 1044
T:
S:
'''
from typing import List


class Solution:
    ################################################
    # Binary Search + Rabin-Karp, rolling hash
    # The simplest solution for Python is to convert string to integer array 
    # of ascii-values.
    def search2(self, L: int, a: int, modulus: int, n: int, nums: List[int]) -> str:
        """
        Rabin-Karp with polynomial rolling hash.
        Search a substring of given length
        that occurs at least 2 times.
        @return start position if the substring exits and -1 otherwise.
        """
        # compute the hash of string S[:L]
        h = 0
        for i in range(L):
            h = (h * a + nums[i]) % modulus
              
        # already seen hashes of strings of length L
        seen = {h} 
        # const value to be used often : a**L % modulus
        aL = pow(a, L, modulus) 
        for start in range(1, n - L + 1):
            # compute rolling hash in O(1) time
            h = (h * a - nums[start - 1] * aL + nums[start + L - 1]) % modulus
            if h in seen:
                return start
            seen.add(h)
        return -1
        
    def longestRepeatingSubstring2(self, S: str) -> str:
        n = len(S)
        # convert string to array of integers
        # to implement constant time slice
        nums = [ord(S[i]) - ord('a') for i in range(n)]
        # base value for the rolling hash function
        a = 26
        # modulus value for the rolling hash function to avoid overflow
        modulus = 2**24
        
        # binary search, L = repeating string length
        left, right = 1, n
        while left <= right:
            L = left + (right - left) // 2
            if self.search(L, a, modulus, n, nums) != -1:
                left = L + 1
            else:
                right = L - 1
               
        return left - 1
    
    
    ################################################
    # dp
    def search3(self, L: int, n: int, S: str) -> str:
        n = len(S)
        S = '#' + S
        dp = [[0 for _ in range(n+1)] for _ in range(n+1)]
        res = 0
        
        for i in range(1, n+1):
            for j in range(1, n+1):
                if i != j and S[i] == S[j]:
                    dp[i][j] = dp[i-1][j-1] + 1
                    res = max(dp[i][j], res)
        return res
    
    
    ################################################
    # Binary Search + Hashset of Hashes of Already Seen Strings
    # S: O(N) for hashset
    def search1(self, L: int, n: int, S: str) -> str:
        """
        Search a substring of given length
        that occurs at least 2 times.
        @return start position if the substring exits and -1 otherwise.
        """
        seen = set()
        for start in range(0, n - L + 1):
            tmp = S[start:start + L]
            h = hash(tmp)
            if h in seen:
                return start
            seen.add(h)
        return -1
        
    def longestRepeatingSubstring1(self, S: str) -> str:
        n = len(S)
        
        # binary search, L = repeating string length
        left, right = 1, n
        while left <= right:
            L = left + (right - left) // 2
            if self.search1(L, n, S) != -1:
                left = L + 1
            else:
                right = L - 1
               
        return left - 1
    
    
    ################################################
    # Binary Search + Hashset of Already Seen Strings
    # T: O(NlogN), O((N-L)*L) for duplicate check, up to O(logN) checks
    # worse case O(N^2), where L ~ N/2
    # S: O(N^2) for hashset
    # Note that if there is a duplicate substring of length k, that means 
    # that there is a duplicate substring of length k - 1.
    def search(self, L: int, n: int, S: str) -> str:
        """
        Search a substring of given length that occurs at least 2 times.
        @return start position if the substring exits and -1 otherwise.
        """
        seen = set()
        for start in range(0, n - L + 1):
            tmp = S[start:start + L]
            if tmp in seen:
                return start
            seen.add(tmp)
        return -1
        
        
    def longestRepeatingSubstring(self, S: str) -> str:
        n = len(S)
        
        # binary search, L = repeating string length
        left, right = 1, n
        while left <= right:
            L = left + (right - left) // 2
            if self.search(L, n, S) != -1: # duplicates found
                left = L + 1 # to find longer substrings
            else:
                right = L - 1
               
        return left - 1