`算法竞赛题解` `LeetCode` 1044. 最长重复子串

`算法竞赛题解` `LeetCode` 1044. 最长重复子串 2023-03-22 1029

题目描述

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

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

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

示例 2：
输入：s = "abcd"
输出：""

提示：

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

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

定义二分定义域为: 子串的长度 [1, N-1]
定义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
if( calc( mid) = true)){ l = mid;