题目链接

题目描述

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

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

示例 1：
输入：s = "banana"
输出："ana"

示例 2：
输入：s = "abcd"
输出：""
1
2
3
4
5
6
7

提示：

• 2 <= s.length <= 1e5
• s 由小写英文字母组成

题解

看到 最长, 最多, 最少, 最…, 一定要首要想到 二分

1. 定义二分定义域为: 子串的长度 [1, N-1]
2. 定义calc( x)为: 是否存在长度为x的重复子串
   … calc的定义是长度等于, 不是大于等于! calc函数, 是对应的具体的算法!
   … 如果定义为>=, 并没有一个直接的具体的确切的算法可以处理, 还得进行拆分子问题. 因为>=x, 可能是x, x+1, x+2, ...很多情况.
   … 而定义为=, 则算法为: O(n)扫描所有长为K的子串, 看有没有相同的. 这个问题定义是清晰的 是确切的
   … 是有这个算法的. (即通过对子串进行哈希成ULL的数, 放到set集合里, 然后去询问set集合)
   calc = false, x > ans
calc = true, x = ans
calc = true, x < ans (这里很重要! 比如答案是abc 和 abc, 则ab 和 ab也是, a 和 a也是)
   符合布尔二段性
   calc = false, x > ans
calc = true, x <= ans
3. if( calc( mid) = true)){ l = mid;