1044.最长重复子串

链接：1044.最长重复子串
难度：Hard
标签：字符串、二分查找、后缀数组、滑动窗口、哈希函数、滚动哈希
简介：返回 任意一个 可能具有最长长度的重复子串。如果 s 不含重复子串，那么答案为 "" 。

题解 1 - typescript

• 编辑时间：2021-12-23
• 执行用时：9236ms
• 内存消耗：60.3MB
• 编程语言：typescript
• 解法介绍：二分答案。

function check(s: string, n: number, num: number): string {
  let left = 0;
  let right = num;
  let str = s.substring(left, right);
  const set = new Set([str]);
  while (right < n) {
    str = s.substring(++left, ++right);
    if (set.has(str)) return str;
    set.add(str);
  }
  return '';
}
function longestDupSubstring(s: string): string {
  const n = s.length;
  let left = 0;
  let right = n;
  let ans = '';
  while (left < right) {
    const mid = (left + right + 1) >> 1;
    const str = check(s, n, mid);
    if (str === '') right = mid - 1;
    else {
      left = mid;
      ans = str;
    }
  }
  return ans;
}