跳到主要内容

1 篇博文 含有标签「滚动哈希」

查看所有标签

· 阅读需 5 分钟

1、题干​

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

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

 

示例 1：

输入：s = "banana"
输出："ana"

示例 2：

输入：s = "abcd"
输出：""

 

提示：

  • 2 <= s.length <= 3 * 104
  • s 由小写英文字母组成

卷不动了，滑动窗口交了

2、执行结果​

1.png

3、解题思路​

使用滑动窗口处理，如果当前窗口字符串长度大于已找到的最长子串长度，且在原字符串的末尾能找到另一个窗口字符串，则当前窗口字符串可以更新为最长子串；重复该动作直至窗口闭合。

  • 最长重复子串记为maxStr，窗口左右边界分别记为i和j，窗口内的字符串记为curStr
  • 当窗口curStr的长度大于maxStr或者右边界j越界时，窗口左边界右移i++，并移除窗口curStr起始位置的字母
  • 当窗口curStr的长度不大于maxStr且右边界j未越界时
    • 在窗口curStr末尾追加右边界之后的字母s[j]，并将窗口右边界右移j++
    • 若窗口curStr的长度大于maxStr且在字符串s尾部找到另一个curStr，则更新maxStr
  • 最后返回maxStr

4、代码​

var longestDupSubstring = function (s) {
  let maxStr = '',curStr = '';
  for (let i = 0, j = 0; i < s.length; i++) {
    curStr = curStr.replace(s[i - 1], '');
    while (curStr.length <= maxStr.length && j < s.length) {
      curStr += s[j], j++;
      if (curStr.length > maxStr.length && s.lastIndexOf(curStr) > i) maxStr = curStr;
    }
  }
  return maxStr;
};

5、优化​

评论区有同学表示Java和C++用这个思路会超时，可能有几个方面原因：

  • 1、可能Node.js的下限比较低（受限于语言执行效率），所以Node.js能过其他不行
  • 2、字符串操作方法replace和+=，Java这里应该可以用StringBuilder优化，C++不太清楚能否优化
  • 3、字符串索引方法lastIndexOf没有限制边界，最坏情况下会完整遍历原字符串，但是窗口扫过的字符串实际是不需要遍历的；改成下面这样限制查找起点能快700ms~1000ms左右
 if (curStr.length > maxStr.length && s.indexOf(curStr, i + 1) > -1) maxStr = curStr;

还可以考虑手写索引方法，另外引入哈希表做缓存避免重复遍历；尝试了下，用例64（30000个v的字符串）超时，这个时候简单的缓存策略是完全失效的。

附上优化后的完整代码，只需修改 lastIndexOf 那一行

var longestDupSubstring = function (s) {
    let maxStr = '', curStr = '';
    for (let i = 0, j = 0; i < s.length; i++) {
        curStr = curStr.replace(s[i - 1], '');
        while (curStr.length <= maxStr.length && j < s.length) {
            curStr += s[j], j++;
            if (curStr.length > maxStr.length && s.indexOf(curStr, i + 1) > -1) maxStr = curStr;
        }
    }
    return maxStr;
};

整体调整，更简洁的版本：

var longestDupSubstring = function (s) {
    let maxStr = '';
    for (let i = 0, j = 0; i < s.length; i++) {
        while (j - i <= maxStr.length && j < s.length && ++j) {
            if (j - i <= maxStr.length) continue;
            const curStr = s.slice(i, j);
            if (s.indexOf(curStr, i + 1) > -1) maxStr = curStr;
        }
    }
    return maxStr;
};