# Leetcode 1044 - Longest Duplicate Substring

`Note:`

- This is a really hard question.
- When a substr with length
`L`

is a repeated str of s, then $L_0 < L$ is also a substr of s. - Based on this attribute, we can use
`binary search`

. - In binary search, we use
`mid`

as the length to do`sliding windows`

, and if we find it’s indeed a repeated substr, we update`left`

so next`mid`

will become longer. If not, we update`right`

to shrink the size of sliding window. - The key part is how to efficiently check if
`a`

is`b`

‘s repeated substr? - If use normal method, it’d be
`O(n*len)`

which is not optimal. Let me introduce`rabin-karp`

algorithm, a`rolling hash`

method. - It looks like
- $Hash = c_1 * b^{len-1} + c_2 * b^{len-2} + c_3 * b^{len-3} + … + c_{len} * b^{0}$.
`b`

is a random base we chose.`c`

is ASCII code.

- From this, we can get a unique
`hash`

for every substr. However, when`sliding window`

reaches size`k`

and we want to`eliminate`

the first char, it’d be time consuming if we just recalculate the whole again. - So, we need to precalculate the
`max term = B^(len-1)`

in this polynomial. - In addition, overflow is not avoidable, so we need to do
`MOD`

with a big prime number. - Last, single hash can lead to
`key collision`

, so we need`double hash`

.

`Question:`

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: s = "banana" |

`Code:`

1 | /** |