Given a string S, consider all duplicated substrings: (contiguous) substrings of S that occur 2 or more times.  (The occurrences may overlap.)
Return any duplicated substring that has the longest possible length.  (If S does not have a duplicated substring, the answer is "".)
 
Example 1:
Input: "banana"
Output: "ana"

Example 2:
Input: "abcd"
Output: ""

 
Note:

2 <= S.length <= 10^5
S consists of lowercase English letters.

Difficulty: interview

Starter code:

class Solution:
    def longestDupSubstring(self, S: str) -> str:
        

Solutions:
class Solution:
    def longestDupSubstring(self, S):
        nums, N = [ord(c) - ord('a') for c in S], len(S)
        BASE, MOD = 26, 2**32
        def check(L):
            cur_hash, seen = 0, set()
            for val in nums[:L]:
                cur_hash = (cur_hash * BASE + val) % MOD
            seen.add(cur_hash)
            X = pow(BASE, L-1, MOD)
            for idx, val in enumerate(nums[L:]):
                cur_hash -= nums[idx] * X
                cur_hash = (cur_hash * BASE + val) % MOD
                if cur_hash in seen:
                    return idx + 1
                seen.add(cur_hash)
            return -1
        low, high = 1, N + 1
        start = 0
        while low < high:
            mid = (low + high)//2
            idx = check(mid)
            if idx != -1:
                low = mid + 1
                start = idx
            else:
                high = mid
        return S[start: start + low - 1]


class Solution:
    def longestDupSubstring(self, S: str) -> str:
        
        def has_duplicate(m, S):
            val, Mod = 0, 2**63-1
            for i in range(m):
                val = (26*val + ord(S[i])) % Mod
            
            d = set([val])
            const = 26**m % Mod
            for i in range(m, len(S)):
                val = (26*val + ord(S[i]) - ord(S[i-m])*const) % Mod
                if val in d: return i-m+1
                d.add(val)
            return -1
        
        l, r = 0, len(S)
        start, length = -1, 0
        while l<=r:
            mid = l + (r-l)//2
            idx = has_duplicate(mid, S)
            if idx!=-1:
                l = mid + 1
                start, length = idx, mid
            else:
                r = mid - 1
                
        if start==-1: return ''
        return S[start:start+length]


class Solution:
    def longestDupSubstring(self, S: str) -> str:
        A = [ord(c) for c in S]
        mod = 2**63-1
        
        lo = 0
        hi = len(S)
        res = 0
        
        def test(sz):
            val = 0
            p = pow(26,sz,mod)
            for i in range(sz):
                val = val*26+A[i]
                val %= mod
            seen = {val}
            for i in range(sz, len(A)):
                val = val*26+A[i]-A[i-sz]*p
                val = val%mod
                if val in seen:
                    return i-sz+1
                seen.add(val)
            return -1     
        
        while lo < hi:
            mid = (lo+hi)//2
            pos = test(mid)
            if not pos >= 0:
                hi = mid
            else:
                res = pos
                lo = mid+1
        
        return S[res:res+lo-1]
        


class Solution:
    def longestDupSubstring(self, S: str) -> str:
        def check(L):
            base = 26
            modulo = 2**32
            AL = base**L%modulo
            hk = 0
            for i in range(L):
                hk = hk*base + nums[i]
            hk %= modulo
            hm = {hk:0}
            for i in range(L, len(S)):
                hk = (hk*base-nums[i-L]*AL+nums[i])%modulo
                if hk in hm and S[i-L+1:i+1]==S[hm[hk]:hm[hk]+L]:
                    return i-L+1
                hm[hk] = i-L+1
                
            return -1
        
        nums = [ord(c)-ord('a') for c in S]
        res = -1
        s, e = 1, len(S)
        while s<=e:
            m = s+(e-s)//2
            pos = check(m)
            if pos!=-1:
                res = pos
                s = m+1
            else:
                e = m-1
                
        return S[res:res+e]


class Solution:
    def longestDupSubstring(self, S: str) -> str:
        def test(L):
            base = 26
            modulus = 2**32
            AL = base**L%modulus
            hk = 0
            for i in range(L):
                hk=hk*base+nums[i]
            hk%=modulus
            hs=set([hk])
            
            for i in range(L, len(S)):
                hk = hk*base-nums[i-L]*AL+nums[i]
                hk%=modulus
                if hk in hs:
                    return i-L+1
                hs.add(hk)
        
        nums = [ord(c)-ord('a') for c in S]
        start, end = 1, len(S)
        res = -1
        while start<=end:
            mid = start+(end-start)//2
            pos = test(mid)
            
            if pos:
                res = pos
                start = mid+1
            else:
                end = mid-1
            
        return S[res:res+end]

class Solution:
    def longestDupSubstring(self, S: str) -> str:
        
        n=len(S)
        mod=10**30
        ord_a=97
        
        def find_len_k_dup(k):
            hash_val=0
            seen=set()
            for i in range(k):
                hash_val=(hash_val*26+(ord(S[i])-ord_a))%mod
            seen.add(hash_val)
            power=26**k%mod
            
            for i in range(1,n-k+1):
                hash_val=((hash_val*26-(ord(S[i-1])-ord_a)*power)%mod+(ord(S[i+k-1])-ord_a))%mod
                if hash_val in seen:
                    return i
                seen.add(hash_val)
            return None
            
#         self.s=S
#         self.n=len(S)
#         def find_len_k_dup(length):
#             hash_value = 0
#             mod_value = 8000*(2**30) # a big number should be okay, if you change the number it might cause a wrong answer
#             seen = set()
#             for i in range(length):
#                 hash_value = (hash_value*26+ord(self.s[i])-ord('a'))%mod_value # get the hash value
#             seen.add(hash_value)
#             tmp = pow(26, length)%mod_value
#             for i in range(1,self.n-length+1):
#                 # get the moving hash 
#                 hash_value = ((hash_value*26 - (ord(self.s[i-1])-ord('a'))*tmp)%mod_value+ord(self.s[i+length-1])-ord('a'))%mod_value
#                 if hash_value in seen:
#                     return i
#                 else:
#                     seen.add(hash_value)
#             return None
        
        
                
        
        low=0
        high=len(S)
        res=''
        while low<high:
            
            mid=(low+high)//2
            idx=find_len_k_dup(mid)
            #print(candidate)
            if idx is not None:
                res=S[idx:idx+mid]
                low=mid+1
            else:
                high=mid
        return res

from functools import reduce
class Solution:
    def longestDupSubstring(self, S: str) -> str:
        A = [ord(c) - ord('a') for c in S]
        mod = 2**63 - 1
        def isDuplicate(len_s):
            p = pow(31, len_s, mod)
            seen = collections.defaultdict(list)
            cur = reduce(lambda x,y: (x*31+y)%mod, A[:len_s])
            seen[cur].append(0)
            for j in range(1, len(A)-len_s+1):
                cur = (cur*31 - A[j-1]*p + A[j+len_s-1])%mod
                if cur in seen:
                    for i in seen[cur]:
                        if S[i:i+len_s] == S[j:j+len_s]:
                            return j
                seen[cur].append(j)
            return 0
        
        l, r = 1, len(S)-1
        ans = ''
        while l <= r:
            mid = l + (r-l)//2
            pos = isDuplicate(mid)
            if pos:
                ans = S[pos:pos+mid]
                l = mid + 1
            else:
                r = mid -1
        return ans 
                
                


from functools import reduce
class Solution:
    def longestDupSubstring(self, S: str) -> str:
        A = [ord(c) - ord('a') for c in S]
        mod = 2**63 - 1
        
        def test(L):
            p = pow(26, L, mod)
            cur = reduce(lambda x, y: (x * 26 + y) % mod, A[: L], 0)
            seen = set()
            seen.add(cur)
            for i in range(L, len(A)):
                cur = (cur * 26 + A[i] - A[i - L] * p) % mod
                if cur in seen:
                    return i - L + 1
                seen.add(cur)
        
        res, lo, hi = 0, 0, len(S)
        while lo + 1 < hi:
            mid = lo + (hi - lo) // 2
            pos = test(mid)
            if pos:
                lo = mid
            else:
                hi = mid
        
        if test(hi):
            pos = test(hi)
            return S[pos: pos + hi]
        pos = test(lo)
        return S[pos: pos + lo]


class Solution:
    def longestDupSubstring(self, S):
        nums = [ord(c) - ord('a') for c in S]
        #BASE, MOD = 113, 1000000007
        BASE, MOD = 26, 2**32
        def check(L):
            cur_hash, seen = 0, set()
            for val in nums[:L]:
                cur_hash = ((cur_hash * BASE) + val) % MOD
            seen.add(cur_hash)
            X = pow(BASE, L-1, MOD) # (BASE ** (L-1)) % MOD
            for i, val in enumerate(nums[L:]):
                # cur_hash -= nums[i] * (BASE ** (L-1))
                cur_hash -= nums[i] * X
                cur_hash = ((cur_hash * BASE) + val) % MOD
                if cur_hash in seen:
                    return i + 1
                seen.add(cur_hash)
            return -1
        low, high = 1, len(S) + 1
        res = 0
        while low < high:
            mid = (low + high)//2
            idx = check(mid)
            if idx != -1:
                low = mid + 1
                res = idx
            else:
                high = mid
        return S[res: res + low-1]
        
        #while low <= high:
        #    mid = (low + high)//2
        #    idx = check(mid)
        #    if idx != -1:
        #        low = mid + 1
        #        res = idx
        #    else:
        #        high = mid - 1
        #return S[res: res + low-1]


class Solution:
    def longestDupSubstring(self, S: str) -> str:
        def checkSubstrings(size):
            hashed = 0
            pow_mult = pow(26, size) % mod
            
            for i in range(size):
                hashed *= 26
                hashed += char_vals[i]
            
            hashed %= mod
            seen = {hashed}
            
            for i in range(size, len(S)):
                hashed = (hashed * 26 - char_vals[i-size] * pow_mult + char_vals[i]) % mod
                if hashed in seen:
                    return i-size+1
                seen.add(hashed)
            
            return None

        s, f = 0, len(S)
        longest = 0
        
        char_vals = [ord(c) - ord('a') for c in S]
        mod = pow(2, 63) - 1
        
        while s < f:
            m = s + (f-s+1) // 2
            longest_check = checkSubstrings(m)
            if longest_check:
                longest = longest_check
                s = m
            else:
                f = m-1
        
        return S[longest:longest+s]


class Solution:
    def longestDupSubstring(self, S: str) -> str:
        # def RabinKarp(text, M, q):
        #     if M == 0: return True
        #     h, t, d = (1<<(8*M-8))%q, 0, 256
        #     dic = defaultdict(list)
        #     for i in range(M): 
        #         t = (d * t + ord(text[i]))% q
        #     dic[t].append(i-M+1)
        #     for i in range(len(text) - M):
        #         t = (d*(t-ord(text[i])*h) + ord(text[i + M]))% q
        #         for j in dic[t]:
        #             if text[i+1:i+M+1] == text[j:j+M]:
        #                 return (True, text[j:j+M])
        #         dic[t].append(i+1)
        #     return (False, \"\")


        def check(sz):
            seen = defaultdict(list)
            cur, base, MOD = 0, 256, (1<<31) - 1
            h = (1 << (sz*8)) % MOD
            for i in range(sz):
                cur *= base
                cur += ord(S[i])
                cur %= MOD
            seen[cur].append(0)
            for i in range(sz,len(S)):
                cur *= base
                cur += ord(S[i])
                cur -= ord(S[i-sz])*h 
                cur %= MOD
                for j in seen[cur]:
                    if S[j:j+sz] == S[i-sz+1:i+1]:
                        return True, S[i-sz+1:i+1]
                seen[cur].append(i-sz+1)
            return False, ''

        lo, hi = 1, len(S)
        res = ''
        # MOD = (1<<31) - 1
        while lo <= hi:
            mid = (lo+hi)//2
            flag, tmp = check(mid)
            # flag, tmp = RabinKarp(S, mid, q)
            if flag:
                lo = mid + 1
                res = tmp
                # print(mid,res)
            else:
                hi = mid - 1
        # print(lo,hi)
        return res 


# class Solution:
#     def RabinKarp(self,text, M, q):
#         if M == 0: return True
#         h, t, d = (1<<(8*M-8))%q, 0, 256

#         dic = defaultdict(list)

#         for i in range(M): 
#             t = (d * t + ord(text[i]))% q

#         dic[t].append(i-M+1)

#         for i in range(len(text) - M):
#             t = (d*(t-ord(text[i])*h) + ord(text[i + M]))% q
#             for j in dic[t]:
#                 if text[i+1:i+M+1] == text[j:j+M]:
#                     return (True, text[j:j+M])
#             dic[t].append(i+1)
#         return (False, \"\")

#     def longestDupSubstring(self, S):
#         beg, end = 0, len(S)
#         q = (1<<31) - 1 
#         Found = \"\"
#         while beg + 1 < end:
#             mid = (beg + end)//2
#             isFound, candidate = self.RabinKarp(S, mid, q)
#             if isFound:
#                 beg, Found = mid, candidate
#             else:
#                 end = mid

#         return Found


class Solution:
    def search(self, S, mid) -> str:
        n = len(S)
        # convert string to array of integers to implement constant time slice
        self.nums = [ord(S[i]) - ord('a') for i in range(n)]
        # base value for the rolling hash function
        base = 26
        # mod value for the rolling hash function to avoid overflow
        MOD = 2**32
    
        # compute the hash of string S[:L]
        hash_ = 0
        for i in range(mid):
            hash_ = (hash_ * base + self.nums[i]) % MOD
              
        # already visited hashes of strings of length L
        visited = {hash_}
        # const value to be used often : a**L % mod
        aL = pow(base, mid, MOD)
        for start in range(1, n - mid + 1):
            # compute rolling hash in O(1) time
            hash_ = (hash_ * base - self.nums[start - 1] * aL + self.nums[start + mid - 1]) % MOD
            if hash_ in visited:
                return start
            visited.add(hash_)
        return -1
        
    def longestDupSubstring(self, S: str) -> str:
        n = len(S)
        # convert string to array of integers to implement constant time slice
        self.nums = [ord(S[i]) - ord('a') for i in range(n)]
        # base value for the rolling hash function
        base = 26
        # mod value for the rolling hash function to avoid overflow
        MOD = 2**32
        
        # binary search, L = repeating string length
        left, right = 1, n
        while left <= right:
            mid = left + (right - left) // 2
            if self.search(S, mid) != -1:
                left = mid + 1
            else:
                right = mid - 1
               
        start = self.search(S, left - 1)
        return S[start: start + left - 1]
    
    
    
    


class Solution:
    def longestDupSubstring(self, S: str) -> str:
        
        def rk(m):
            
            nonlocal idx
            mp = {}
            p = b**(m-1)
            p%=mod
            
            y = 0
            for i in range(m):
                y = y*b+num[i]
            y%=mod    
            
            mp[y] = 0
                
            for i in range(1, n-m+1):
                y = ((y-num[i-1]*p%mod)*b%mod+num[i-1+m])%mod
                #y = (y-num[i-1]*p)*b+num[i-1+m]
                
                if y in mp:
                    idx = i
                    return 0
                else:
                    mp[y]=i
            
            return 1
                
            

        n = len(S)
        b = 26                      # no need to be 128
        #mod = 10**9+7              # too small => conflict
        mod = 2**32                 # here
        
        z = ord('a')
        num = [ ord(S[i])-z for i in range(n)]
        
        l=1
        r=n
        idx = 0  # last found duplicate                 
        while l<r:
            
            m = (l+r)//2
            
            if rk(m)>0:
                r = m
            else:
                l = m+1
        
        return S[idx:idx+l-1]
        
        


class Solution:
    def longestDupSubstring(self, S: str) -> str:
        
        def rk(m):
            
            mp = {}

            p = b**(m-1)
            p%=mod
            
            y = 0
            for i in range(m):
                y = y*b+num[i]
            y%=mod    
            
            mp[y] = 0
                
            for i in range(1, n-m+1):
                y = ((y-num[i-1]*p%mod)*b%mod+num[i-1+m])%mod
                #y = (y-num[i-1]*p)*b+num[i-1+m]
                
                if y not in mp:
                    mp[y]=i
                else:
                    return i
            
            return n
                
            
        
        
        n = len(S)
        
        b = 26                      # no need to be 128
        
        #mod = 10**9+7              # too small => conflict
        mod = 2**32                 # here
        
        num = []
        for i in range(n):
            num.append(ord(S[i])-ord('a'))
        
        l=1
        r=n
        
        while l<r:
            
            m = (l+r)//2
            
            if rk(m)==n:
                r = m
            else:
                l = m+1
       
        
        x = l-1
        
        if x==0:
            return ''
        
        k = rk(x)
        
        return S[k:k+x]
        
        


class Solution:
    def longestDupSubstring(self, S: str) -> str:
        
        def rk(m):
            
            nonlocal idx
            st = set()
            p = b**(m-1)
            p%=mod
            
            y = 0
            for i in range(m):
                y = y*b+num[i]
            
            y%=mod
            
            st.add(y)
                
            for i in range(1, n-m+1):
                y = ((y-num[i-1]*p%mod)*b%mod+num[i-1+m])%mod
                #y = (y-num[i-1]*p)*b+num[i-1+m]
                
                if y in st:
                    idx = i
                    return 0
                else:
                    st.add(y)
            
            return 1
                
            

        n = len(S)
        b = 26                      # no need to be 128
        #mod = 10**9+7              # too small => conflict
        mod = 2**32                 # here
        
        z = ord('a')
        num = [ ord(S[i])-z for i in range(n)]
        
        l=1
        r=n
        idx = 0  # last found duplicate                 
        while l<r:
            
            m = (l+r)//2
            
            if rk(m)>0:
                r = m
            else:
                l = m+1
        
        return S[idx:idx+l-1]
        
        


from functools import reduce
class Solution:
    def longestDupSubstring(self, S: str) -> str:
        
        
        A = [ord(c) - ord('a') for c in S]
        mod = 2**63 - 1

        def test(L):
            # print(26, L, mod)
            p = pow(26, L, mod)
            cur = reduce(lambda x, y: (x * 26 + y) % mod, A[:L], 0)
            seen = {cur}
            for i in range(L, len(S)):
                cur = (cur * 26 + A[i] - A[i - L] * p) % mod
                if cur in seen: return i - L + 1
                seen.add(cur)
        res, lo, hi = 0, 0, len(S)
        while lo < hi:
            mi = (lo + hi + 1) // 2
            pos = test(mi)
            if pos:
                lo = mi
                res = pos
            else:
                hi = mi - 1
        return S[res:res + lo]
        
#         s = [ord(num) - ord(\"a\") for num in S]
        
#         mod = 10 ** 9 + 7
#         def check(l):
#             cur = 0
#             seen = set()
#             maxBASE = pow(26, l-1, mod)
#             for i in range(len(s)):
#                 if i < l:
#                     cur = (cur * 26 + s[i]) % mod
#                 else:
#                     cur -= maxBASE * s[i-l]
#                     cur = (cur * 26 + s[i]) % mod
#                 if i == l-1:
#                     seen.add(cur)
#                 elif i >= l:
#                     if cur in seen:
#                         return i-l+1
#                     else:
#                         seen.add(cur)
#             return 0
                
                
                
        
#         l = 1
#         r = len(S) - 1
#         res = -1
#         while l < r:
#             m = (l+r) // 2
#             pos = check(m)
#             if pos:
#                 l = m 
#                 res = pos
#             else:
#                 r = m - 1
#         return S[res:res + l]
            
        
            


class Solution:
    def longestDupSubstring(self, S):
        nums, N = [ord(c) - ord('a') for c in S], len(S)
        BASE, MOD = 26, 2**32
        def check(L):
            cur_hash, seen = 0, set()
            for val in nums[:L]:
                cur_hash = (cur_hash * BASE + val) % MOD
            seen.add(cur_hash)
            X = pow(BASE, L-1, MOD)
            for idx, val in enumerate(nums[L:]):
                cur_hash -= nums[idx] * X
                cur_hash = (cur_hash * BASE + val) % MOD
                if cur_hash in seen:
                    return idx + 1
                seen.add(cur_hash)
            return -1
        low, high = 1, N + 1
        start = 0
        while low < high:
            mid = (low + high)//2
            idx = check(mid)
            if idx != -1:
                low = mid + 1
                start = idx
            else:
                high = mid
        return S[start: start + low - 1]

class Solution:
    def longestDupSubstring(self, S: str) -> str:
        self.s=S
        self.n=len(S)
        def find_len_k_dup(length):
            hash_value = 0
            mod_value = 7919*(2**30) # a big number should be okay, if you change the number it might cause a wrong answer
            seen = set()
            for i in range(length):
                hash_value = (hash_value*26+ord(self.s[i])-ord('a'))%mod_value # get the hash value
            seen.add(hash_value)
            tmp = pow(26, length)%mod_value
            for i in range(1,self.n-length+1):
                # get the moving hash 
                hash_value = (hash_value*26 - (ord(self.s[i-1])-ord('a'))*tmp+mod_value+ord(self.s[i+length-1])-ord('a'))%mod_value
                if hash_value in seen:
                    return i
                else:
                    seen.add(hash_value)
            return None
                
        
        low=0
        high=len(S)
        res=''
        while low<high:
            
            mid=(low+high)//2
            idx=find_len_k_dup(mid)
            #print(candidate)
            if idx is not None:
                res=S[idx:idx+mid]
                low=mid+1
            else:
                high=mid
        return res

class Solution:
    def longestDupSubstring(self, S: str) -> str:
        
        lo = 1
        hi = len(S)
        nums = [ord(i) - ord('a') for i in S]
        self.modulus = 2 ** 32
        
        def dup(l):
            seen = set()
            hval = 0
            for i in range(l):
                hval = (hval*26 + nums[i]) % self.modulus
            seen.add(hval)
            al = pow(26,l,self.modulus)
            for i in range(1,len(S) - l+1):
                hval = (hval*26 - nums[i-1]*al + nums[i+l-1]) % self.modulus
                if hval in seen:
                    return i
                seen.add(hval)
            return -1
        
        start = -1
        while lo <= hi:
            mi = lo + (hi-lo)//2
            begin = dup(mi)
            if begin != -1:
                lo = mi + 1
                start = begin
            else:
                hi = mi - 1
        
        return S[start: start + lo - 1]

class Solution:
    def longestDupSubstring(self, S: str) -> str:
        N = len(S)
        l, r = 1, N
        nums = [ord(x) - ord('a') for x in S]
        KMAX = 2 ** 63 - 1
        def check(m):
            MAXL = pow(26, m, KMAX)
            total = 0
            hashset = set()
            for i in range(m):
                total = (total * 26 + nums[i]) % KMAX
            hashset.add(total)
            for i in range(1, N - m + 1):
                total = (total * 26 - MAXL * nums[i-1] + nums[i + m - 1]) % KMAX
                if total in hashset:
                    return i
                hashset.add(total)
            return -1         
        
        while l < r:
            m = (l + r) // 2
            if check(m) < 0:
                r = m
            else:
                l = m + 1
        idx = check(r - 1)        
        return S[idx: idx + r-1]

class Solution:
    def longestDupSubstring(self, S: str) -> str:
        self.s=S
        self.n=len(S)
        def find_len_k_dup(length):
            hash_value = 0
            mod_value = 8000*(2**30) # a big number should be okay, if you change the number it might cause a wrong answer
            seen = set()
            for i in range(length):
                hash_value = (hash_value*26+ord(self.s[i])-ord('a'))%mod_value # get the hash value
            seen.add(hash_value)
            tmp = pow(26, length)%mod_value
            for i in range(1,self.n-length+1):
                # get the moving hash 
                hash_value = ((hash_value*26 - (ord(self.s[i-1])-ord('a'))*tmp)%mod_value+ord(self.s[i+length-1])-ord('a'))%mod_value
                if hash_value in seen:
                    return i
                else:
                    seen.add(hash_value)
            return None
                
        
        low=0
        high=len(S)
        res=''
        while low<high:
            
            mid=(low+high)//2
            idx=find_len_k_dup(mid)
            #print(candidate)
            if idx is not None:
                res=S[idx:idx+mid]
                low=mid+1
            else:
                high=mid
        return res

from functools import reduce
class Solution:
    def longestDupSubstring(self, S: str) -> str:
        A = [ord(c) - ord('a') for c in S]
        mod = 2**63 - 1

        def test(L):
            p = pow(26, L, mod)
            cur = reduce(lambda x, y: (x * 26 + y) % mod, A[:L], 0)
            seen = {cur}
            for i in range(L, len(S)):
                cur = (cur * 26 + A[i] - A[i - L] * p) % mod
                if cur in seen: return i - L + 1
                seen.add(cur)
        res, lo, hi = 0, 0, len(S)
        while lo + 1 < hi:
            mi = (lo + hi) // 2
            pos = test(mi)
            if pos:
                lo = mi
            else:
                hi = mi
        
        if test(hi):
            res = test(hi)
            return S[res: res + hi]
        elif test(lo):
            res = test(lo)
            return S[res: res + lo]
        # return ''


from functools import reduce
class Solution:
    def longestDupSubstring(self, S):
        def evaluateLength(length):
            power = pow(26, length, mod)
            current = reduce(lambda x, y: (x*26 + y) % mod, ids[:length], 0)
            explored = {current}
            for index in range(length, len(S)):
                current = (current * 26 + ids[index] - ids[index - length] * power) % mod
                if current in explored:
                    return index - length + 1
                explored.add(current)
        
        ids = [ord(character) - ord('a') for character in S]
        mod = 2**63 - 1
        index, low, high = 0, 0, len(S)
        while low < high:
            mid = (high + low + 1) // 2
            position = evaluateLength(mid)
            if position:
                index = position
                low = mid
            else:
                high = mid - 1 
        return S[index:(index+low)]


class Solution:
    def longestDupSubstring(self, S: str) -> str:
        N = len(S)
        l, r = 1, N
        nums = [ord(x) - ord('a') for x in S]
        KMAX = 2 ** 63 - 1
        def check(m):
            MAXL = pow(26, m, KMAX)
            total, hashset = 0, set()
            for i in range(m):
                total = (total * 26 + nums[i]) % KMAX
            hashset.add(total)
            for i in range(1, N - m + 1):
                total = (total * 26 - MAXL * nums[i-1] + nums[i+m-1]) % KMAX
                if total in hashset:
                    return i
                hashset.add(total)
            return -1
        
        while l < r:
            m = (l + r) // 2
            if check(m) < 0:
                r = m
            else:
                l = m + 1
        idx = check(r - 1)        
        return S[idx: idx + r-1]

class Solution:
    def longestDupSubstring(self, S: str) -> str:
        
        def check(s, L):
            n = len(s)
            BASE = 26
            MOD = 1 << 61 - 1
            P = pow(26, L, MOD)
            cur = 0
            seen = defaultdict(list)
            
            for i in range(len(s)):
                cur = (cur*BASE + ord(s[i]) - ord('a')) % MOD
                if i >= L:
                    cur = (cur - (ord(s[i-L]) - ord('a')) * P) % MOD
                
                if i >= L - 1:
                    if cur in seen:
                        cur_str = s[i-L+1:i+1]
                        for j in seen[cur]:
                            pre_str = s[j-L+1:j+1]
                            if cur_str == pre_str:
                                return cur_str
                    seen[cur].append(i)       
            return ''
            
            
        lo, hi = 1, len(S)
        ans = ''
        while lo < hi:
            mid = (lo + hi) // 2
            temp = check(S, mid)
            if temp:
                ans = temp
                lo = mid + 1
            else:
                hi = mid

        return ans


class Solution:
    def longestDupSubstring(self, S: str) -> str:
        p = 239017
        pows = [[1], [1]]
        hsh = [[0], [0]]
        mods = [int(1e9) + 7, int(1e9) + 9]
        for ch in S:
            for i in range(len(mods)):
                hsh[i].append((hsh[i][-1] + ord(ch) * pows[i][-1]) % mods[i])
                pows[i].append((pows[i][-1] * p) % mods[i])               
        l = 0
        r = len(S)
        substrs = {}
        ans = ''
        while r - l > 1:
            m = (r + l) // 2
            found = False
            for i in range(0, len(S) - m + 1):
                h0 = ((hsh[0][i + m] - hsh[0][i]) * pows[0][-(i + 1)]) % mods[0]
                h1 = ((hsh[1][i + m] - hsh[1][i]) * pows[1][-(i + 1)]) % mods[1]
                if (h0, h1) in substrs:
                    found = True
                    ans = S[i: i + m]
                    break
                else:
                    substrs[(h0, h1)] = True
            if found:
                l = m
            else:
                r = m
            substrs.clear()
        return ans

class Solution:
    def longestDupSubstring(self, S: str) -> str:
        
        mod = 2 ** 31 - 1
        base = 26
        
        def get_ord(char: str):
            return ord(char) - ord('a')
        
        def find_duplicate(length) -> str:
            hashes = {}
            h = 1
            for i in range(length - 1):
                h = (h * base) % mod

            cur = 0
            for i in range(length):
                cur = (cur * base + get_ord(S[i])) % mod
            
            hashes[cur] = [0]

            for i in range(1, len(S) - length + 1):
                cur = ((cur - (get_ord(S[i-1]) * h)) * base + get_ord(S[i + length - 1])) % mod
                if cur in hashes:
                    for idx in hashes[cur]:
                        if S[idx: idx + length] == S[i: i + length]:
                            return S[i: i + length]
                    hashes[cur].append(i)
                else:
                    hashes[cur] = [i]
            return ''
        
        
        def helper(start, end):
            res = ''
            while start < end:
                length = (start + end) // 2 + 1
                r = find_duplicate(length)
                if len(r) > len(res):
                    res = r
                if not r:
                    end = length - 1
                else:
                    start = length
            return res

        return helper(0, len(S) - 1)

class Solution:
    def findRepSubstrGivenLength(self, nums: List[int], l:int, base:int, modulus:int) -> int:
        
        n = len(nums)
        
        h = 0
        for i in range(l):
            h = (h * base + nums[i]) % modulus
            
        seen = {h}
            
        for start in range(1, n-l+1):
            h = (h * base - nums[start - 1] * pow(base, l, modulus) + nums[start + l - 1]) % modulus
            
            if h in seen:
                return start
            
            seen.add(h)
            
        return -1    
    
    
    def longestDupSubstring(self, S: str) -> str:
        if not S:
            return ''
                
        nums = [ord(S[i]) - ord('a') for i in range(len(S))]
        
        base = 26
        modulus = 2**32
        
        left = 1
        right = len(S)
        
        while left <= right:
            mid = left + (right - left) // 2
            
            if self.findRepSubstrGivenLength(nums, mid, base, modulus) != -1:
                left = mid + 1
            else:
                right = mid -1
                
        start = self.findRepSubstrGivenLength(nums, left-1, base, modulus)
        
        return S[start: start + left -1]    
        
        
        
'''
class Solution:
    class Node:
        def __init__(self, v='*'): 
            self.value = v
            self.next = dict()
            self.occurences = set()
                   
                
    def print_tree(self, node, indentation):
        print(indentation + str(node.value) + \": \" + str(node.occurences))

        for v in node.next.keys():
            self.print_tree(node.next[v], indentation + '\\t')
        
        
    def getNode(self, node, v):
        if v not in node.next.keys():
            node.next[v] = self.Node(v)

        return node.next[v]


    def AddOccurences(self, node, i, S):
        node.occurences.add(i)

        if len(node.occurences) == 2:
            for o in node.occurences:
                if o + 1 < len(S):
                    self.AddOccurences(self.getNode(node, S[o+1]), o+1, S)


        if len(node.occurences)>2:
            if i + 1 < len(S):
                self.AddOccurences(self.getNode(node, S[i+1]), i+1, S)

        
    def getLongestDuplicate(self, node):
        maxSubstring = ''
        
        for v in node.next.keys():
            if len(node.next[v].occurences)>1:

                childSubstring = self.getLongestDuplicate(node.next[v])
                if len(childSubstring) + 1 > len(maxSubstring):
                    maxSubstring = v + childSubstring
                        
        return maxSubstring
    
    
    def longestDupSubstring(self, S: str) -> str:
        if not S:
            return 0
        
        if len(set(S)) == 1:
            return S[0:len(S)-1]

        root = self.Node()

        for i in range(len(S)):
            self.AddOccurences(self.getNode(root, S[i]), i, S)

        #self.print_tree(root, '')
        maxDepthDuplicates = self.getLongestDuplicate(root)
        
        return maxDepthDuplicates
'''        

class Solution:
    def longestDupSubstring(self, S):
        nums = [ord(c) - ord('a') for c in S]
        #BASE, MOD = 113, 1000000007
        BASE, MOD = 26, 2**32
        def check(L):
            cur_hash, seen = 0, set()
            for val in nums[:L]:
                cur_hash = ((cur_hash * BASE) + val) % MOD
            seen.add(cur_hash)
            X = pow(BASE, L-1, MOD) # (BASE ** (L-1)) % MOD
            for i, val in enumerate(nums[L:]):
                # cur_hash -= nums[i] * (BASE ** (L-1))
                cur_hash -= nums[i] * X
                cur_hash = ((cur_hash * BASE) + val) % MOD
                if cur_hash in seen:
                    return i + 1
                seen.add(cur_hash)
            return -1
        low, high = 1, len(S)
        res = 0
        while low < high:
            mid = (low + high)//2
            idx = check(mid)
            if idx != -1:
                low = mid + 1
                res = idx
            else:
                high = mid
        return S[res: res + low-1]
        
        #while low <= high:
        #    mid = (low + high)//2
        #    idx = check(mid)
        #    if idx != -1:
        #        low = mid + 1
        #        res = idx
        #    else:
        #        high = mid - 1
        #return S[res: res + low-1]


class Solution:
    def longestDupSubstring(self, S: str) -> str:
        def check(Val):
            base, modulus = 26, 2**32
            AL = base**Val%modulus
            hk = 0
            for i in range(Val):
                hk = hk*base + ord(S[i])-ord('a')
            hk %= modulus
            hm = {hk: 0}
            
            for i in range(Val, N):
                hk = hk*base - (ord(S[i-Val])-ord('a'))*AL + ord(S[i]) - ord('a')
                hk %= modulus
                if hk in hm and S[hm[hk]:hm[hk]+Val]==S[i-Val+1:i+1]:
                    return i-Val+1
                
                hm[hk] = i-Val+1
            # print(mid, hm)
            
        N = len(S)
        start, end = 1, N
        res = 0
        while start<=end:
            mid = start+(end-start)//2
            pos = check(mid)
            if pos:
                res = pos
                start = mid+1
            else:
                end = mid-1
                
        return S[res:res+end]

class Solution:
    def longestDupSubstring(self, S: str) -> str:
        n = len(S)
        BASE = 26
        MOD = (1 << 63) - 1
        POWS = [1] * n
        for i in range(1, n):
            POWS[i] = (POWS[i - 1] * BASE) % MOD
        def search(k):
            seen = set()
            h = 0
            for i in range(k):
                h = (h * BASE + ord(S[i]) - 97) % MOD
            seen.add(h)
            for i in range(k, n):
                h = ((h - (ord(S[i - k]) - 97) * POWS[k - 1]) * BASE + ord(S[i]) - 97) % MOD
                s = S[i - k + 1:i + 1]
                if h in seen:
                    return i
                seen.add(h)
            return -1
        
        l, r = 0, n - 1
        while l <= r:
            m = (l + r) // 2
            if search(m) >= 0:
                l = m + 1
            else:
                r = m - 1
        if r < 0:
            return ''
        i = search(r)
        return S[i - r + 1:i + 1]

class Solution:
    def search(self, L: int, a: int, modulus: int, n: int, nums: List[int]) -> str:
        h = 0
        for i in range(L):
            h = (h * a + nums[i]) % modulus
        
        seen = {h}
        
        aL = pow(a, L, modulus)
        
        for start in range(1, n-L + 1):
            h = (h * a - nums[start - 1]* aL + nums[start + L - 1]) % modulus
            if h in seen:
                return start
            seen.add(h)
        return -1
    
    def longestDupSubstring(self, S: str) -> str:
        n = len(S)
        nums = [ord(S[i]) - ord('a') for i in range(n)]
        a = 26
        modulus = 2 ** 32
        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
        start = self.search(left -1, a, modulus, n, nums)
        return S[start: start + left - 1]


from collections import defaultdict
class Solution:
    def longestDupSubstring(self, S: str) -> str:
        l, h = 2, len(S)-1
        res = ''
        while l <= h:
            m = l + (h-l) // 2
            cand = self.find_dup_substr_len_k(S, m)
            if cand:
                res = cand
                l = m+1
            else:
                h = m-1
        return res
    
    def find_dup_substr_len_k(self, s, k):
        MOD = (1 << 63) - 1
        BASE = 26
        D = pow(BASE, k-1, MOD)
        hash_val = 0
        seen = defaultdict(set)
        
        for i in range(len(s)):
            # update the sliding hash value
            if i >= k:
                char_offset = ord(s[i-k]) - ord('a') 
                hash_val = (hash_val - char_offset * D) % MOD
            char_offset = ord(s[i]) - ord('a') 
            hash_val = (hash_val * BASE + char_offset) % MOD
            
            # check hash collision and return string if duplicate found
            if i >= k-1:
                if hash_val in seen:
                    cand_i = s[i-k+1:i+1]
                    for j in seen[hash_val]:
                        cand_j = s[j-k+1:j+1]
                        if cand_i == cand_j:
                            return cand_i
                seen[hash_val].add(i)
        return ''


class Solution:
    def longestDupSubstring(self, S: str) -> str:
        
        def code(t):
            return ord(t) - ord('a')+1
        def check(length):
            seen = collections.defaultdict(list)
            
            MOD = 10 ** 9 + 7
            P = 113
            INV_P = pow(P, MOD-2, MOD)

            h = 0
            power = 1
            '''
            h1 = s[0]p^0+s[1]p^1+s[2]p^2 +...+s[length-1]p^(length-1)
            move next:
            h2 = s[1]p^0+s[2]p^1+s[3]p^2 +...+s[length]p^(length-1)
            
            h2 = (h1 - S[i-length+1])*INV_P % MOD
            
            '''
            for i, x in enumerate(S):
                h = (h + power*code(x)) % MOD 
                if i < length-1:
                    power = power * P % MOD
                else:
                    # start: i-(length-1)
                    if h in seen:
                        for j in seen[h]:
                            if S[i-(length-1):i+1] == S[j:j+length]:
                                return S[j:j+length], True
                    seen[h].append(i-(length-1))
                    h = (h-code(S[i-(length-1)]))*INV_P % MOD
            
            return '', False
        
        res = ''
        l, r = 1, len(S)-1
        while l <= r:
            mid = (l+r)//2
            sub, is_check = check(mid)
            if is_check:
                res = sub
                l = mid + 1
            else:
                r = mid - 1
        
        return res

class Solution:
    
    def find(self ,s , m) :
        
        seen = collections.defaultdict(list)
        
        mod = 1<<63 -1
        base = 26
        d = pow(26,m-1,mod)
        chal = 0
        
        for i in range(len(s)) :
            
            if i >= m :
                l_chal = ord(s[i-m]) - ord('a')
                chal = ( chal - l_chal*d)%mod
                
            l_chal = ord(s[i]) - ord('a')
            chal = (chal*base + l_chal)%mod
            
            if i >= m-1 :
                s_i = s[i-m+1 : i +1]
                if chal in seen :
                    
                    for j in seen[chal] :
                        s_j = s[j-m+1 : j+1]
                        if s_j == s_i :
                            return s_i
                        
                else :
                    seen[chal].append(i)
                    
        return ''
            
    def longestDupSubstring(self, S: str) -> str:
        
        l = 2 
        h = len(S) -1
        ans = ''
        
        while l <= h :
            m = (l+h)//2
            
            s = self.find(S ,m)
            
            if s != '' :
                ans = s
                l = m+1
            
            else :
                h = m-1
                
        return ans

class Solution:
    def longestDupSubstring(self, S):
        nums, N = [ord(c) - ord('a') for c in S], len(S)
        BASE, MOD = 26, 2**32
        def check(L):
            cur_hash, seen = 0, set()
            for val in nums[:L]:
                cur_hash = (cur_hash * BASE + val) % MOD
            seen.add(cur_hash)
            X = pow(BASE, L-1, MOD)
            for idx, val in enumerate(nums[L:], start = L):
                cur_hash -= nums[idx - L] * X
                cur_hash = (cur_hash * BASE + val) % MOD
                if cur_hash in seen:
                    return idx - L + 1
                seen.add(cur_hash)
            return -1
        low, high = 1, N + 1
        start = 0
        while low < high:
            mid = (low + high)//2
            idx = check(mid)
            if idx != -1:
                low = mid + 1
                start = idx
            else:
                high = mid
        return S[start: start + low - 1]

from collections import defaultdict
class Solution:
    def longestDupSubstring(self, S: str) -> str:
        mod = 10 ** 9 + 7
        def get_rep(l: int) -> str:
            mp = defaultdict(list) # key: hash_code, value: list of start indexes of substrings
            a = 13
            sofar = 0
            factor = 1
            for i in range(l):
                sofar = (sofar * a + ord(S[i])) % mod
                factor = (factor * a) % mod
            mp[sofar].append(0)
            for i in range(l, len(S)):
                sofar = (sofar * a + ord(S[i]) - factor * ord(S[i - l])) % mod
                if sofar in mp:
                    for j in mp[sofar]:
                        if S[j: j + l] == S[i - l + 1: i + 1]:
                            return S[i - l + 1: i + 1]
                mp[sofar].append(i - l + 1)
            return None
        
        low, high = 0, len(S) - 1
        ans = None
        while low <= high:
            mid = (low + high) // 2
            res = get_rep(mid)
            if res is None:
                high = mid - 1
            else:
                ans = res
                low = mid + 1
        return ans if ans is not None else ''


class Solution:
    def longestDupSubstring(self, S: str) -> str:
        def search(m, MOD):
            h = 0
            for i in range(m):
                h = (h * 26 + nums[i]) % MOD
            s = {h}
            aL = pow(26, m, MOD)
            for pos in range(1, n - m + 1):
                h = (h * 26 - nums[pos - 1] * aL + nums[pos + m - 1]) % MOD
                if h in s:
                    return pos
                s.add(h)
            return -1

        n = len(S)
        nums = [ord(c) - ord('a') for c in S]
        l, r = 1, n
        pos = -1
        MOD = 2**63 - 1
        while l <= r:
            m = (l + r) // 2
            cur = search(m, MOD)
            if cur != -1:
                l = m + 1
                pos = cur
            else:
                r = m - 1
        return S[pos: pos + l - 1]        

class Solution:
    def longestDupSubstring(self, S: str) -> str:
        base, mod = 26, 2**63 - 1
        n = len(S)
        A = [ord(ch) - ord('a') for ch in S]
        def k_dup(k):
            curr = 0
            for i in range(k):
                curr = (curr * base + A[i]) % mod
            seen = {curr}
            for i in range(1, n - k + 1):
                curr = ( base*curr - pow(base, k, mod)*A[i-1] + A[i+k-1]) % mod
                if curr in seen:
                    return i
                seen.add(curr)
            return 0
        l, r, ans = 0, n, 0
        while l < r:
            mid = (l + r + 1) >> 1
            pos = k_dup(mid)
            # print(pos, mid)
            if pos:
                l = mid
                ans = pos
            else:
                r = mid - 1
        return S[ans:ans + l]
        


class Solution:
    def longestDupSubstring(self, S):
        nums = [ord(c) - ord('a') for c in S]
        BASE, MOD = 26, 2**32               # Wrong: BASE, MOD = 113, 1000000007, too small
        def check(L):
            cur_hash, seen = 0, set()
            for val in nums[:L]:
                cur_hash = ((cur_hash * BASE) + val) % MOD
            seen.add(cur_hash)
            X = pow(BASE, L-1, MOD)         # much faster than (BASE ** (L-1)) % MOD
            for i, val in enumerate(nums[L:]):
                # cur_hash -= nums[i] * (BASE ** (L-1))
                cur_hash -= nums[i] * X
                cur_hash = ((cur_hash * BASE) + val) % MOD
                if cur_hash in seen:
                    return i + 1
                seen.add(cur_hash)
            return -1
        low, high = 1, len(S) + 1
        res = 0
        while low < high:
            mid = (low + high)//2
            idx = check(mid)
            if idx != -1:
                low = mid + 1
                res = idx
            else:
                high = mid
        return S[res: res + low-1]
    
class Solution:
    def longestDupSubstring(self, S):
        N = len(S)
        def check(length):
            seen = set()
            for i in range(N - length):
                hashS = hash(S[i:i+length+1])
                if hashS in seen:
                    return i
                seen.add(hashS)
            return 0

        low, high = 0, N
        idx = 0
        while low < high:
            mid = (low + high)//2
            start = check(mid)
            if start:
                low = mid + 1
                idx = start
            else:
                high = mid
        return S[idx:idx + low]

class Solution:
    def search(self, L: int, base: int, MOD: int, n: int, nums: List[int]) -> str:
        # compute the hash of string S[:L]
        h = 0
        for i in range(L):
            h = (h * base + nums[i]) % MOD
              
        # already seen hashes of strings of length L
        seen = {h} 
        # const value to be used often : a**L % mod
        aL = pow(base, L, MOD) 
        for start in range(1, n - L + 1):
            # compute rolling hash in O(1) time
            h = (h * base - nums[start - 1] * aL + nums[start + L - 1]) % MOD
            if h in seen:
                return start
            seen.add(h)
        return -1
        
    def longestDupSubstring(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
        base = 26
        # mod value for the rolling hash function to avoid overflow
        MOD = 2**32
        
        # binary search, L = repeating string length
        left, right = 1, n
        while left <= right:
            mid = left + (right - left) // 2
            if self.search(mid, base, MOD, n, nums) != -1:
                left = mid + 1
            else:
                right = mid - 1
               
        start = self.search(left - 1, base, MOD, n, nums)
        return S[start: start + left - 1]
    
    
    
    


class Solution:
    def longestDupSubstring(self, S: str) -> str:
        n = len(S)
        low = 0
        high = n-1
        
        nums = [ord(S[i]) - ord('a') for i in range(n)]
        
        def findDuplicate(L):
            # compute the hash of string S[:L]
            h = 0
            a = 26
            modulus = 2**32
            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
        
        res = ''
        while low < high:
            mid = (low + high + 1)//2
            start = findDuplicate(mid)
            if start != -1:
                low = mid
                res = S[start:start+mid] 
            else:
                high = mid-1
        return res

class Solution:
    def longestDupSubstring(self, S: str) -> str:
        
        l = 0
        r = len(S)
        base = 26
        mod = 2**32
        res = [0, 0]
        nums = [ord(n) - ord('a') for n in S]

        
        while l < r:
            
            mid = (l+r) // 2
            h = 0
            
            for i in range(0, mid):
                h = (h*base + nums[i]) % mod
                
            dups = set([h])
            remove = pow(base, mid, mod)
            
            for i in range(1, len(nums) - mid + 1):
                h = (h*base - nums[i-1] * remove + nums[i+mid-1]) % mod
                
                if h in dups:
                    res = [i, i+mid]
                    break
                    
                dups.add(h)
                # print(mid, h)         
            if res[1] - res[0] < mid:
                r = mid
            else:
                l = mid + 1
            
                
        return S[res[0]:res[1]]
                
                


class Solution:
    def longestDupSubstring(self, S: str) -> str:
        low = 0
        high = len(S)-1
        result = ''
        nums = [ord(i) - ord('a') for i in S]
        mod = 2**63-1
        
        def rabin_karp(size):
            power = pow(26,size,mod)
            hash_val = 0
            hash_set = set()
            for i in range(size):
                hash_val = (hash_val*26 + (nums[i]))%mod
            hash_set.add(hash_val)
            for i in range(size, len(S)):
                hash_val = (hash_val*26 - (power*nums[i-size]) + nums[i])%mod
                if hash_val in hash_set:
                    return i-size+1
                else:
                    hash_set.add(hash_val)
            return -1
        while(low <= high):
            mid = low + (high-low)//2
            pos = rabin_karp(mid)
            if pos == -1:
                high = mid - 1
            else:
                result = S[pos:pos+mid]
                low = mid+1
        return result

class Solution:
    def longestDupSubstring(self, S):
        nums = [ord(c) - ord('a') for c in S]
        BASE, MOD = 26, 2**32               # Wrong: BASE, MOD = 113, 1000000007, too small
        def check(L):
            cur_hash, seen = 0, set()
            for val in nums[:L]:
                cur_hash = ((cur_hash * BASE) + val) % MOD
            seen.add(cur_hash)
            X = pow(BASE, L-1, MOD)         # much faster than (BASE ** (L-1)) % MOD
            for i, val in enumerate(nums[L:]):
                # cur_hash -= nums[i] * (BASE ** (L-1))
                cur_hash -= nums[i] * X
                cur_hash = ((cur_hash * BASE) + val) % MOD
                if cur_hash in seen:
                    return i + 1
                seen.add(cur_hash)
            return -1
        low, high = 1, len(S) + 1
        res = 0
        while low < high:
            mid = (low + high)//2
            idx = check(mid)
            if idx != -1:
                low = mid + 1
                res = idx
            else:
                high = mid
        return S[res: res + low-1]

class Solution:
    def longestDupSubstring(self, S: str) -> str:
        n=len(S)
        modulus=2**32
        a=26        
        nums=[ord(c)-ord('a') for c in S]
        def search(L):
            nonlocal a,n,modulus
            aL=pow(a,L,modulus)
            h=0
            for i in range(L):
                h=(h*a+nums[i])%modulus
            seen={h}
            for start in range(1,n-L+1):
                h=(h*a-nums[start-1]*aL+nums[start+L-1])%modulus
                if h in seen:
                    return start
                seen.add(h)
            return -1
        
        l,r=1,n
        while l<=r:
            mid=(l+r)>>1
            if search(mid)!=-1:
                l=mid+1
            else:
                r=mid-1
                        
        start=search(r)        
        return S[start:start+r]

class Solution:
    
    def rabinKarp(self, L, nums):
        h = 0
        a = 26
        MOD = 2**32
        for i in range(L):
            h = (h * a + nums[i]) % MOD
           
        aL = pow(a, L, MOD)
        seen = {h}
        for start in range(1, len(nums)-L+1):
            h = (h *a - nums[start-1] * aL + nums[start+L-1]) % MOD
            if h in seen:
                return start
            seen.add(h)
        return -1
    
    def longestDupSubstring(self, S: str) -> str:   
        nums = [ord(ch)-ord('a') for ch in S]
        l, r = 0, len(S)
        while l < r:
            mid = l + (r-l) // 2
            if self.rabinKarp(mid, nums) != -1:
                l = mid + 1
            else:
                r = mid
        start = self.rabinKarp(l-1, nums)
        return S[start:start+l-1]        
            


from functools import reduce
class Solution:
    def longestDupSubstring(self, S: str) -> str:
        # binary search + string hashing
        from functools import reduce
        A = [ord(c) - ord('a') for c in S]
        mod = 2 ** 63 - 1
        def judge(l):
            p = 26 ** l % mod
            cur = reduce(lambda x, y : (x * 26 + y) % mod, A[:l], 0)
            seen = {cur}
            for i in range(l, len(S)):
                cur = (cur * 26 + A[i] - p * A[i - l]) % mod
                if cur in seen: return i - l + 1
                seen.add(cur)
        
        lo, hi = 0, len(S)
        res = 0
        while lo < hi:
            mi = (lo + hi + 1) // 2
            pos = judge(mi)
            if pos:
                lo = mi
                res = pos
            else:
                hi = mi - 1
        return S[res : res + lo]


class Solution:
    # Use binary search to try out all possible lengths of the subtrings
    # Use a record list to record the hash summation of the substring
    # Use the number of distinct chara as the hash base
    # If two substrings are the same, they should have the same hash summation
    # After minus the before part
    def longestDupSubstring(self, S: str) -> str:
        res = ''
        d,q = len(set(S)), 2**63-1
        record = [0]*len(S)
        for i in range(len(S)):
            if i == 0:record[i] = ord(S[i])
            else:record[i] = (record[i-1]*d+ord(S[i]))%q
        def check(mid):
            h,g = 1,set()
            for i in range(mid):
                h = h*d%q
            for i in range(len(S)-mid+1):
                count = (record[i+mid-1]-record[i-1]*h)%q if i > 0 else record[i+mid-1]
                if count not in g:g.add(count)
                else:return S[i:i+mid]
            return False
        l,r = 0,len(S)-1
        while l<=r:
            mid = (l+r)//2
            temp = check(mid)
            if temp:
                res = temp
                l = mid + 1
            else:r = mid - 1
        return res
        
        
#         res = \"\"
#         d, q = len(set(S)), 2**63-1
#         hashes = [0] * len(S)
#         for i in range(len(S)):
#             if i == 0: hashes[i] = ord(S[i])
#             else: hashes[i] = (hashes[i-1]*d + ord(S[i]))%q
#         l, r = 0, len(S)-1
#         while l <= r:
#             mid = (l+r)//2
#             temp = self.check(S,mid,hashes,d,q)
#             if temp:
#                 res = temp
#                 l = mid + 1
#             else: r = mid - 1
#         return res
    
#     def check(self, S, mid, hashes, d, q):
#         res = set()
#         h, g = 1, 0
#         for i in range(mid):
#             h = (h*d)%q
#         for i in range(len(S)-mid+1):
#             g = (hashes[i+mid-1] - hashes[i-1]*h)%q if i > 0 else hashes[i+mid-1]
#             if g not in res: res.add(g)
#             else: return S[i:i+mid]
#         return False
                
                


class Solution:
    def longestDupSubstring(self, S: str) -> str:
        
        def rk(m):
            
            nonlocal idx
            st = set()
            
            #p = b**(m-1)
            #p%=mod
            p= pow(b,m-1,mod)  # more efficient to mod at each step than work on a long number
            
            y = 0
            for i in range(m):
                y = (y*b+num[i])%mod  # more efficient to mod at each step than work on a long number
                
            st.add(y)
                
            for i in range(1, n-m+1):
                y = ((y-num[i-1]*p%mod)*b%mod+num[i-1+m])%mod
                #y = (y-num[i-1]*p)*b+num[i-1+m]
                
                if y in st:
                    idx = i
                    return 0
                else:
                    st.add(y)
            
            return 1
                
            

        n = len(S)
        b = 26                      # no need to be 128
        #mod = 10**9+7              # too small => conflict
        mod = 2**32                 # here
        
        z = ord('a')
        num = [ ord(S[i])-z for i in range(n)]
        
        l=1
        r=n
        idx = 0  # last found duplicate                 
        while l<r:
            
            m = (l+r)//2
            
            if rk(m)>0:
                r = m
            else:
                l = m+1
        
        return S[idx:idx+l-1]
        
        


p = 2**63 - 1

class Solution:
    def longestDupSubstring(self, S: str) -> str:
        def rabin_karp(mid):
            cur_hash = 0
            for i in range(mid):
                cur_hash = (cur_hash * 26 + nums[i]) % p
            hashes = {cur_hash}
            pos = -1
            max_pow = pow(26, mid, p)
            for i in range(mid, len(S)):
                cur_hash = (26*cur_hash-nums[i-mid]*max_pow + nums[i]) % p
                if cur_hash in hashes:
                    pos = i + 1 - mid
                hashes.add(cur_hash)
            return pos


        low, high = 0, len(S)-1
        end = 0
        start = 0
        nums = [ord(c)-ord('a') for c in S]
        while low <= high:
            mid = (low+high) // 2
            pos = rabin_karp(mid)
            if pos == -1:  # no matching strings found
                high = mid - 1
            else:
                start = pos
                low = mid + 1
        return S[start:start+low-1]


class Solution:
    def longestDupSubstring(self, S: str) -> str:
        def search(m, MOD):
            h = 0
            for i in range(m):
                h = (h * 26 + nums[i]) % MOD
            s = {h}
            aL = pow(26, m, MOD)
            for pos in range(1, n - m + 1):
                h = (h * 26 - nums[pos - 1] * aL + nums[pos + m - 1]) % MOD
                if h in s:
                    return pos
                s.add(h)
            return -1

        n = len(S)
        nums = [ord(c) - ord('a') for c in S]
        l, r = 1, n
        pos = -1
        MOD = 2**63 - 1
        while l <= r:
            m = (l + r) // 2
            cur = search(m, MOD)
            if cur != -1:
                l = m + 1
                pos = cur
            else:
                r = m - 1
        return S[pos: pos + l - 1]

class Solution:
    def longestDupSubstring(self, S: str) -> str:
        N = len(S)
        l, r = 1, N
        nums = [ord(x) - ord('a') for x in S]
        KMAX = 2 ** 63 - 1
        def check(m):
            MAXL = pow(26, m, KMAX)
            total = 0
            hashset = set()
            for i in range(m):
                total = (total * 26 + nums[i]) % KMAX
            hashset.add(total)
            for i in range(1, N - m + 1):
                total = (total * 26 - nums[i-1] * MAXL + nums[i+m-1]) % KMAX
                if total in hashset:
                    return i
                hashset.add(total)
            return -1
        
        while l < r:
            m = (l + r) // 2
            if check(m) < 0:
                r = m
            else:
                l = m + 1
        idx = check(r - 1)        
        return S[idx: idx + r-1]

class Solution:
    def longestDupSubstring(self, S: str) -> str:
        ords = [ord(ch) - 97 for ch in S]
        mod = 2 ** 32
        seen = set()
        
        def has_dup_with_length(length):
            seen.clear()
            p = pow(26, length, mod)
            
            hashed_prefix = 0
            for i in range(length):
                hashed_prefix = (hashed_prefix * 26 + ords[i]) % mod
            seen.add(hashed_prefix)

            for i in range(length, len(S)):
                hashed_prefix = (hashed_prefix * 26 + ords[i] - ords[i - length] * p) % mod
                if hashed_prefix in seen:
                    return i - length + 1
                seen.add(hashed_prefix)
        
        start, lo, hi = 0, 0, len(S) - 1, 
        while lo < hi:
            mid_length = (lo + hi + 1) // 2
            idx = has_dup_with_length(mid_length)
            if idx:
                start = idx
                lo = mid_length
            else:
                hi = mid_length - 1
        return S[start: start + lo]

class Solution:
    def longestDupSubstring(self, S: str) -> str:
        res = ''
        d,q = len(set(S)), 2**63-1
        record = [0]*len(S)
        for i in range(len(S)):
            if i == 0:record[i] = ord(S[i])
            else:record[i] = (record[i-1]*d+ord(S[i]))%q
        def check(mid):
            h,g = 1,set()
            for i in range(mid):
                h = h*d%q
            for i in range(len(S)-mid+1):
                count = (record[i+mid-1]-record[i-1]*h)%q if i > 0 else record[i+mid-1]
                if count not in g:g.add(count)
                else:return S[i:i+mid]
            return False
        l,r = 0,len(S)-1
        while l<=r:
            mid = (l+r)//2
            temp = check(mid)
            if temp:
                res = temp
                l = mid + 1
            else:r = mid - 1
        return res
        
        
#         res = \"\"
#         d, q = len(set(S)), 2**63-1
#         hashes = [0] * len(S)
#         for i in range(len(S)):
#             if i == 0: hashes[i] = ord(S[i])
#             else: hashes[i] = (hashes[i-1]*d + ord(S[i]))%q
#         l, r = 0, len(S)-1
#         while l <= r:
#             mid = (l+r)//2
#             temp = self.check(S,mid,hashes,d,q)
#             if temp:
#                 res = temp
#                 l = mid + 1
#             else: r = mid - 1
#         return res
    
#     def check(self, S, mid, hashes, d, q):
#         res = set()
#         h, g = 1, 0
#         for i in range(mid):
#             h = (h*d)%q
#         for i in range(len(S)-mid+1):
#             g = (hashes[i+mid-1] - hashes[i-1]*h)%q if i > 0 else hashes[i+mid-1]
#             if g not in res: res.add(g)
#             else: return S[i:i+mid]
#         return False
                
                


class Solution:
    def longestDupSubstring(self, S: str) -> str:
        n = len(S)
        nums = [ord(S[i]) - ord('a') for i in range(n)]
        
        def search(position):
            h = 0
            for i in range(position):
                h = (h * 26 + nums[i]) % 2 ** 32
            seen = {h}
            const = 26 ** position % 2 ** 32
            for start in range(1, n - position + 1):
                h = (h * 26 - nums[start - 1] * const + nums[start + position - 1]) % 2 ** 32
                if h in seen:
                    return start
                seen.add(h)
            return -1
        
        left, right = 1, n
        while left <= right:
            pivot = (left + right) // 2
            if search(pivot) != -1:
                left = pivot + 1
            else:
                right = pivot - 1
        start = search(left - 1)
        return S[start: start + left - 1]

class Solution:
    def longestDupSubstring(self, S: str) -> str:
    
        arr = [ord(ch) - ord('a') for ch in S]
        n = len(arr)
        B = 29
        mod = 2**63 - 1
        def exists(L):
            seen = {}
            P = pow(B, L, mod)
            h = 0
            for i in range(n):
                h = (h * B + arr[i]) % mod
                if i >= L:
                    h = (h - arr[i-L] * P) % mod
                if i >= L - 1:
                    if h in seen:
                        return seen[h]
                    seen[h] = i
            return -1
        
        lo, hi = 0, len(S)
        # cand = ''
        pos = -1
        while lo < hi:
            mid = (lo + hi + 1) // 2
            idx = exists(mid)
            if idx != -1:
                lo = mid
                # cand = S[idx - mid + 1: idx + 1]
                pos = idx
            else:
                hi = mid - 1
        return S[pos - lo + 1:pos+1]


class Solution:
    def longestDupSubstring(self, S: str) -> str:
        self.A = [ord(c) - ord('a') for c in S]
        
        start, end = 1, len(S)
        while start + 1 < end:
            mid = (start + end) // 2
            pos = self.check(mid)
            if pos:
                start = mid
            else:
                end = mid

        pos = self.check(end)
        if pos:
            return S[pos: pos + end]
        pos = self.check(start)
        if pos:
            return S[pos: pos + start]
        return ''
    
    def check(self, length):
        mod = 2**63 - 1
        power = pow(26, length, mod)
        
        cur = 0
        for i in range(length):
            cur = (cur * 26 + self.A[i]) % mod
        
        # cur = reduce(lambda x, y: (x * 26 + y) % mod, self.A[:length], 0)
        seen = {cur}
        
        for i in range(length, len(self.A)):
            cur = (cur * 26 + self.A[i] - self.A[i - length] * power) % mod
            if cur in seen:
                return i - length + 1
            seen.add(cur)


class Solution:
    def longestDupSubstring(self, S: str) -> str:
        
        def rk(m):
            
            nonlocal idx
            st = set()
            p = b**(m-1)
            p%=mod
            
            y = 0
            for i in range(m):
                y = (y*b+num[i])%mod
                
            st.add(y)
                
            for i in range(1, n-m+1):
                y = ((y-num[i-1]*p%mod)*b%mod+num[i-1+m])%mod
                #y = (y-num[i-1]*p)*b+num[i-1+m]
                
                if y in st:
                    idx = i
                    return 0
                else:
                    st.add(y)
            
            return 1
                
            

        n = len(S)
        b = 26                      # no need to be 128
        #mod = 10**9+7              # too small => conflict
        mod = 2**32                 # here
        
        z = ord('a')
        num = [ ord(S[i])-z for i in range(n)]
        
        l=1
        r=n
        idx = 0  # last found duplicate                 
        while l<r:
            
            m = (l+r)//2
            
            if rk(m)>0:
                r = m
            else:
                l = m+1
        
        return S[idx:idx+l-1]
        
        


from functools import reduce
class Solution:
    def longestDupSubstring(self, S: str) -> str:
        self.A = [ord(c) - ord('a') for c in S]
        
        start, end = 1, len(S)
        while start + 1 < end:
            mid = (start + end) // 2
            pos = self.check(mid)
            if pos:
                start = mid
            else:
                end = mid

        pos = self.check(end)
        if pos:
            return S[pos: pos + end]
        pos = self.check(start)
        if pos:
            return S[pos: pos + start]
        return ''
    
    def check(self, length):
        mod = 2**63 - 1
        power = pow(26, length, mod)
        
        cur = reduce(lambda x, y: (x * 26 + y) % mod, self.A[:length], 0)
        seen = {cur}
        
        for i in range(length, len(self.A)):
            cur = (cur * 26 + self.A[i] - self.A[i - length] * power) % mod
            if cur in seen:
                return i - length + 1
            seen.add(cur)


from functools import reduce
class Solution:
    def longestDupSubstring(self, S: str) -> str:
        self.A = [ord(c) - ord('a') for c in S]
        
        start, end = 1, len(S)
        while start + 1 < end:
            mid = (start + end) // 2
            pos = self.check(mid)
            if pos:
                start = mid
            else:
                end = mid

        pos = self.check(end)
        if pos:
            return S[pos: pos + end]
        pos = self.check(start)
        if pos:
            return S[pos: pos + start]
        return ''
    
    def check(self, length):
        mod = 2**63 - 1
        power = pow(26, length, mod)
        
        # cur = 0
        # for i in range(length):
        #     cur = (cur * 26 + self.A[i]) % mod
        
        cur = reduce(lambda x, y: (x * 26 + y) % mod, self.A[:length], 0)
        seen = {cur}
        
        for i in range(length, len(self.A)):
            cur = (cur * 26 + self.A[i] - self.A[i - length] * power) % mod
            if cur in seen:
                return i - length + 1
            seen.add(cur)


from functools import reduce
class Solution:
    def longestDupSubstring(self, S: str) -> str:
        self.A = [ord(c) - ord('a') for c in S]
        
        start, end = 1, len(S)
        while start + 1 < end:
            mid = (start + end) // 2
            print(mid)
            pos = self.check(mid)
            print(pos)
            if pos:
                start = mid
            else:
                end = mid
        # print(start, end)
        pos = self.check(end)
        # print(pos)
        if pos:
            return S[pos: pos + end]
        pos = self.check(start)
        if pos:
            return S[pos: pos + start]
        return ''
    
    def check(self, length):
        mod = 2**63 - 1
        power = pow(26, length, mod)
        
        cur = reduce(lambda x, y: (x * 26 + y) % mod, self.A[:length], 0)
        seen = {cur}
        
        for i in range(length, len(self.A)):
            cur = (cur * 26 + self.A[i] - self.A[i - length] * power) % mod
            if cur in seen:
                return i - length + 1
            seen.add(cur)


class Solution:
    def searchLongestStringOfKLen(self, S, total_len, compare_len):
        search_len_hash = 0
        for i in range(compare_len):
            search_len_hash = (search_len_hash * self.uniq + self.nums[i]) %  self.mod

        tmp_hash = {}
        tmp_hash[search_len_hash] = True
        
        remove_old_power = pow(self.uniq,  compare_len, self.mod)
        for i in range(1, total_len-compare_len+1):
            search_len_hash = (search_len_hash * self.uniq - (remove_old_power * self.nums[i-1]) + self.nums[i+compare_len-1] )% self.mod
            if search_len_hash in tmp_hash:
                return i
            tmp_hash[search_len_hash] = True
            
        return -1
        
    
    def longestDupSubstring(self, S: str) -> str:
        ls = len(S)
        end = ls
        start = 1 
        mid = 0
        self.nums = []
        for i in range(ls):
            self.nums.append(ord(S[i]) - ord('a'))

        self.uniq = 26
        self.mod = 2**32
        while start <= end:
            mid = start + (end-start)//2
            if self.searchLongestStringOfKLen(S, ls, mid) != -1:
                start = mid +  1
            else :
                end = mid - 1
        
        ds_sp = self.searchLongestStringOfKLen(S, ls, start -1)
        return S[ds_sp:ds_sp+start-1]

def check(arr, n, l, mod):
    p = pow(26, l, mod)
    window_hash = 0
    hash_set = set()
    for i in range(l):
        window_hash = (26 * window_hash + arr[i]) % mod
    hash_set.add(window_hash)

    for i in range(1, n - l + 1):
        window_hash = (window_hash * 26 - (arr[i - 1]*p) + arr[i + l - 1])%mod
        if window_hash in hash_set:
            return i
        hash_set.add(window_hash)

    return False


class Solution:
    def longestDupSubstring(self, S: str) -> str:
        
        n = len(S)
        min_length, max_length = 1, n
        ans, prev_len = 0, 0
        mod = (1 << 63) - 1
        nums = [ord(S[i]) - ord('a') for i in range(n)]

        while min_length <= max_length:
            mid_length = int((max_length + min_length)/2)
            start = check(nums, n, mid_length, mod)
            if start != False:
                if prev_len < mid_length:
                    ans = start
                    prev_len = mid_length
                min_length = mid_length + 1
            else:
                max_length = mid_length - 1
        
        return S[ans:ans + prev_len]


class Solution:
    def longestDupSubstring(self, S: str) -> str:
        n=len(S)
        modulus=2**56
        a=26        
        nums=[ord(c)-ord('a') for c in S]
        def search(L):
            nonlocal a,n,modulus
            aL=pow(a,L,modulus)
            h=0
            for i in range(L):
                h=(h*a+nums[i])%modulus
            seen={h}
            for start in range(1,n-L+1):
                h=(h*a-nums[start-1]*aL+nums[start+L-1])%modulus
                if h in seen:
                    return start
                seen.add(h)
            return -1
        
        l,r=1,n
        while l<=r:
            mid=(l+r)>>1
            if search(mid)!=-1:
                l=mid+1
            else:
                r=mid-1
                        
        start=search(r)        
        return S[start:start+r]

class Solution:
    def longestDupSubstring(self, S: str) -> str:
        n = len(S)
        chars = [ord(c) - 97 for c in S]
        BASE = 26
        MOD = (1 << 63) - 1
        POWS = [1] * n
        for i in range(1, n):
            POWS[i] = (POWS[i - 1] * BASE) % MOD
        def search(k):
            seen = set()
            h = 0
            for i in range(k):
                h = (h * BASE + chars[i]) % MOD
            seen.add(h)
            for i in range(k, n):
                h = ((h - chars[i - k] * POWS[k - 1]) * BASE + chars[i]) % MOD
                if h in seen:
                    return i
                seen.add(h)
            return -1
        
        l, r = 0, n - 1
        k = 0
        while l < r:
            m = (l + r + 1) // 2
            i = search(m)
            if i >= 0:
                k = i
                l = m
            else:
                r = m - 1
        return S[k - l + 1:k + 1]

class Solution:
    def longestDupSubstring(self, S: str) -> str:
        n = len(S)
        chars = [ord(c) - 97 for c in S]
        BASE = 26
        MOD = (1 << 63) - 1
        POWS = [1] * n
        for i in range(1, n):
            POWS[i] = (POWS[i - 1] * BASE) % MOD
        def search(k):
            seen = set()
            h = 0
            for i in range(k):
                h = (h * BASE + chars[i]) % MOD
            seen.add(h)
            for i in range(k, n):
                h = ((h - chars[i - k] * POWS[k - 1]) * BASE + chars[i]) % MOD
                if h in seen:
                    return i
                seen.add(h)
            return -1
        
        l, r = 0, n - 1
        while l <= r:
            m = (l + r) // 2
            if search(m) >= 0:
                l = m + 1
            else:
                r = m - 1
        if r < 0:
            return ''
        i = search(r)
        return S[i - r + 1:i + 1]

class Solution:
    def longestDupSubstring(self, S: str) -> str:
        p = 31
        m = 100000000003

        pows = [1] * len(S)
        invPows = [1] * len(S)
        for i in range(1, len(S)):
            pows[i] = pows[i-1] * p % m
            invPows[i] = pow(pows[i], -1, m)

        h = [0] * (len(S) + 1)
        for i in range(len(S)):
            h[i+1] = (h[i] + (ord(S[i]) - ord('a') + 1) * pows[i]) % m

        def hasDup(S, sublen):
            seen = set()
            for i in range(len(S)- sublen + 1):
                if (hs := (h[i + sublen] - h[i]) * invPows[i] % m) in seen:
                    return (i, sublen)
                seen.add(hs)
            return (0, 0)

        ans = None
        lo, hi = 1, len(S)
        while lo < hi:
            mid = (lo + hi) // 2
            if (s := hasDup(S, mid))[1]:
                lo = mid + 1
                ans = s
            else:
                hi = mid
        return S[ans[0]:ans[0]+ans[1]] if ans else ''

class Solution:
    def longestDupSubstring(self, S: str) -> str:
        def search(m, MOD):
            h = 0
            for i in range(m):
                h = (h * 26 + nums[i]) % MOD
            s = {h}
            aL = pow(26, m, MOD)
            for pos in range(1, n - m + 1):
                h = (h * 26 - nums[pos - 1] * aL + nums[pos + m - 1]) % MOD
                if h in s:
                    return pos
                s.add(h)
            return -1
        
        n = len(S)
        nums = [ord(c) - ord('a') for c in S]
        # find length of longest duplicate substring
        l, r = 1, n
        pos = 0
        MOD = 2**63 - 1 # use largest positive of 8 byte integer
        while l <= r:
            m = (l + r) // 2
            # search if there's duplicate for length m substring
            cur = search(m, MOD)
            if cur != -1:
                l = m + 1
                pos = cur
            else:
                r = m - 1
        return S[pos: pos + l - 1]

from collections import defaultdict
from functools import reduce


class Solution:
    def longestDupSubstring(self, S: str) -> str:
        mod = (1 << 63 - 1)
        A = [ord(c) - ord('a') for c in S]
        
        def find_dup_of_length(L):
            p = pow(26, L, mod)
            h = reduce(lambda x, y: (x * 26 + y) % mod, A[:L], 0)
            seen = defaultdict(list)
            seen[h].append(0)
            
            for i in range(L, len(S)):
                h = (h * 26 + A[i] - p * A[i-L]) % mod
                for start in seen[h]:
                    if S[start:start+L] == S[i-L+1:i+1]:
                        return start
                
                seen[h].append(i-L+1)
        
        start = 0
        length = 0
        low, high = 1, len(S)
        while low < high:
            mid = low + (high - low) // 2
            pos = find_dup_of_length(mid)
            if pos is not None:
                start = pos
                length = mid
                low = mid + 1
            else:
                high = mid
                
        return S[start:start+length]