LeetCode 1044 - 最长重复子串
题目描述
给你一个字符串 s ,考虑其所有重复子串:即 s 的(连续)子串,在 s 中出现 2 次或更多次。这些出现之间可能存在重叠。返回任意一个可能具有最长长度的重复子串。
解题思路
这题也是不能用动态规划做的子串问题。实际还是要通过遍历来做,利用了如果存在某个长度为 M
的重复子串,那么一定有长度为 N(N<M)
的子串这样的思想。
具体实现方法
1. 每次指定一个子串的长度,然后从开头开始,去检查所有该长度的子串
2. 比如这次检查是否有长度为 10 的重复子串,然后从开头开始去检查所有的长度为 10 的子串
3. 每次都计算出 HASH 值,然后判断是否 HASH 值存在过
4. 由于是滑动窗口,即左边出去右边进来,这样就可以用旧的 HASH 值很快的计算新的 HASH 值
优化方法
遍历就是遍历指定长度。相当于每次指定一个长度,如果存在,那么就去指定一个更长的长度。所以用二分比较好。