<p>Given a string <code>s</code>, consider all <em>duplicated substrings</em>: (contiguous) substrings of s that occur 2 or more times.&nbsp;The occurrences&nbsp;may overlap.</p>

<p>Return <strong>any</strong> duplicated&nbsp;substring that has the longest possible length.&nbsp;If <code>s</code> does not have a duplicated substring, the answer is <code>&quot;&quot;</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<pre><strong>Input:</strong> s = "banana"
<strong>Output:</strong> "ana"
</pre><p><strong class="example">Example 2:</strong></p>
<pre><strong>Input:</strong> s = "abcd"
<strong>Output:</strong> ""
</pre>
<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>2 &lt;= s.length &lt;= 3 * 10<sup>4</sup></code></li>
	<li><code>s</code> consists of lowercase English letters.</li>
</ul>

class Solution:
    def longestDupSubstring(self, s: str) -> str:
        Mod = 2**63 - 1
        n = len(s)
        nums = [ord(c) - ord('a') for c in s]
        
        left = 1
        right = n - 1
        res = ""

        def search(L):
            h = 0
            a = 26
            al = pow(a, L, Mod)  # 這裡變數名統一
            seen = {}

            # 計算長度為 L 的子字串的哈希值
            for i in range(L):
                h = (h * a + nums[i]) % Mod
            seen[h] = 0

            # 計算後續長度為 L 的子字串哈希值
            for i in range(1, n - L + 1):
                # 更新哈希值
                h = (h * a - nums[i - 1] * al + nums[i + L - 1]) % Mod
                if h in seen:
                    idx = seen[h]
                    if nums[idx:idx+L] == nums[i:L+i]:
                        return s[i:L+i]
                seen[h] = i

            return ""

        while left <= right:
            mid = left + (right - left) // 2
            dup = search(mid)

            if dup:
                if len(dup) > len(res):
                    res = dup
                left = mid + 1
            else:
                right = mid - 1

        return res
21800