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.

Source: leetcode | Difficulty: MEDIUM
Tags: String algorithms

Sorting

Amortized analysis

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
		low = 0
		high = len(S)
		res = ''
		while low < high:
			mid = (low + high) // 2
			idx = find_len_k_dup(mid)
			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: 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 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 = ''
		while lo <= hi:
			mid = (lo + hi) // 2
			(flag, tmp) = check(mid)
			if flag:
				lo = mid + 1
				res = tmp
			else:
				hi = mid - 1
		return res


class Solution:

	def search(self, S, mid) -> str:
		n = len(S)
		self.nums = [ord(S[i]) - ord('a') for i in range(n)]
		base = 26
		MOD = 2 ** 32
		hash_ = 0
		for i in range(mid):
			hash_ = (hash_ * base + self.nums[i]) % MOD
		visited = {hash_}
		aL = pow(base, mid, MOD)
		for start in range(1, n - mid + 1):
			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)
		self.nums = [ord(S[i]) - ord('a') for i in range(n)]
		base = 26
		MOD = 2 ** 32
		(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
				if y in mp:
					idx = i
					return 0
				else:
					mp[y] = i
			return 1
		n = len(S)
		b = 26
		mod = 2 ** 32
		z = ord('a')
		num = [ord(S[i]) - z for i in range(n)]
		l = 1
		r = n
		idx = 0
		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
				if y not in mp:
					mp[y] = i
				else:
					return i
			return n
		n = len(S)
		b = 26
		mod = 2 ** 32
		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:
		self.s = S
		self.n = len(S)

		def find_len_k_dup(length):
			hash_value = 0
			mod_value = 7919 * 2 ** 30
			seen = set()
			for i in range(length):
				hash_value = (hash_value * 26 + ord(self.s[i]) - ord('a')) % mod_value
			seen.add(hash_value)
			tmp = pow(26, length) % mod_value
			for i in range(1, self.n - length + 1):
				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)
			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]


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:

		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(1000000000.0) + 7, int(1000000000.0) + 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:

	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
		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)):
			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
			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
			for (i, x) in enumerate(S):
				h = (h + power * code(x)) % MOD
				if i < length - 1:
					power = power * P % MOD
				else:
					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


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)
			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)
			if pos:
				l = mid
				ans = pos
			else:
				r = mid - 1
		return S[ans:ans + l]


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):
			h = 0
			a = 26
			modulus = 2 ** 32
			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
		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)
			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: 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:
		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:

	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


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:
				high = mid - 1
			else:
				start = pos
				low = mid + 1
		return S[start:start + low - 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:
		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))
		pos = -1
		while lo < hi:
			mid = (lo + hi + 1) // 2
			idx = exists(mid)
			if idx != -1:
				lo = mid
				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
		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 = 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:
		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 ''


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]