longest-duplicate-substring

java

python3

python

javascript

typescript

csharp

golang

kotlin

swift

rust

ruby

dart

scala

elixir

erlang

racket

cangjie

bash

mysql

mssql

postgresql

oraclesql

pythondata

Algorithms

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

Return any 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>.

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

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

第 136 场周赛

weekly-contest-136

longestDupSubstring

首席工程师

Longest Duplicate Substring

String

Binary Search

Suffix Array

Suffix Tree

Sliding Window

Hash Function

Rolling Hash

Boyer–Moore 算法

扩展 KMP

Suffix Automato

给你一个字符串 <code>s</code> ，考虑其所有 重复子串 ：即&nbsp;<code>s</code> 的（连续）子串，在 <code>s</code> 中出现 2 次或更多次。这些出现之间可能存在重叠。

返回 任意一个 可能具有最长长度的重复子串。如果 <code>s</code> 不含重复子串，那么答案为 <code>""</code> 。

&nbsp;

示例 1：

<pre>
输入：s = "banana"
输出："ana"
</pre>

示例 2：

<pre>
输入：s = "abcd"
输出：""
</pre>

&nbsp;

提示：

<ul>
	<li><code>2 &lt;= s.length &lt;= 3 * 104</code></li>
	<li><code>s</code> 由小写英文字母组成</li>
</ul>