1044. 最长重复子串

给出一个字符串 S，考虑其所有重复子串（S 的连续子串，出现两次或多次，可能会有重叠）。
返回任何具有最长可能长度的重复子串。（如果 S 不含重复子串，那么答案为 “”。）

示例 1：
输入：“banana” 输出：“ana”
示例 2：
输入：“abcd” 输出：“”

提示：

  1. 2 <= S.length <= 10^5
  2. S 由小写英文字母组成。

思路：
考虑到数据范围，应该是O(nlogn)级别的时间复杂度，先考虑能否二分，对于本题，如果长度为k的子串有重复，那么任何长度小于k的子串也一定重复。
即存在最长重复子串，长度小于等于该长度的子串都有重复，但长度大于它的子串不会重复，故可以使用二分。
第二个问题，如何在每个二分中使得时间复杂度为O(n)，即如何快速找出该长度的子串是否有重复？
使用哈希表 + 字符串哈希，字符串哈希保证了O(n)的时间复杂度，哈希表用于辅助记录以出现过的子串的哈希值。

本题帮助复习了字符串哈希的细节

  1. class Solution {
  2.     long[] h = new long[100010], pow = new long[100010];
  3.     final int P = 131;
  4.     int ans = -1;
  5.     public String longestDupSubstring(String s) {
  6.         int n = s.length();
  7.         pow[0] = 1;
  9.         for (int i = 1; i <= n; i++) {
  10.             h[i] = h[i - 1] * P + s.charAt(i - 1);
  11.             pow[i] = pow[i - 1] * P;
  12.         }
  14.         int l = 1, r = n - 1;
  15.         while (l < r) {
  16.             int mid = l + r + 1 >> 1;
  17.             if (check(s, mid))
  18.                 l = mid;
  19.             else 
  20.                 r = mid - 1;
  21.         }
  22.         check(s, l);
  23.         if (ans == -1)
  24.             return "";
  25.         return s.substring(ans - 1, ans + l - 1);
  26.     }
  28.     boolean check(String s, int len) {
  29.         Set<Long> set = new HashSet();
  30.         for (int i = len; i <= s.length(); i++) {
  31.             long a = get(i - len + 1, i);
  32.             if (set.contains(a)) {
  33.                 ans = i - len + 1;
  34.                 return true;
  35.             }
  36.             else
  37.                 set.add(a);
  38.         }
  39.         return false;
  40.     }
  41.     long get(int l, int r) {
  42.         return h[r] - h[l - 1] * pow[r - l + 1];
  43.     }
  44. }

718. 最长重复子数组

思路：
方法1：类似于最长公共子序列，只是换成了连续而已
方法2：字符串哈希 + 二分

  1. // DP
  2. class Solution {
  3.     public int findLength(int[] nums1, int[] nums2) {
  4.         int n = nums1.length, m = nums2.length;
  5.         int[][] f = new int[n + 1][m + 1];
  7.         int res = 0;
  8.         for (int i = 1; i <= n; i++) {
  9.             for (int j = 1; j <= m; j++) {
  10.                 if (nums1[i - 1] == nums2[j - 1])
  11.                     f[i][j] = f[i - 1][j - 1] + 1;
  12.                 res = Math.max(f[i][j], res);
  13.             }
  14.         }
  15.         return res;
  16.     }
  17. }
  1. // 方法2
  2. class Solution {
  3.     long[] pow = new long[1010];
  4.     public int findLength(int[] nums1, int[] nums2) {
  5.         int n = nums1.length, m = nums2.length;
  6.         long x = 0, p = 13331;
  7.         pow[0] = 1;
  8.         for (int i = 1; i <= 1000; i++)
  9.             pow[i] = p * pow[i - 1];
  10.         long[] a1 = new long[n + 1];
  11.         long[] a2 = new long[m + 1];
  14.         for (int i = 1; i <= n; i++) {
  15.             a1[i] = a1[i - 1] * p + (nums1[i - 1] + 1);
  16.         }
  18.         for (int i = 1; i <= m; i++) {
  19.             a2[i] = a2[i - 1] * p + (nums2[i - 1] + 1);
  20.         }
  21.         int l = 0, r = Math.min(n, m);
  22.         while (l < r) {
  23.             int mid = l + r + 1 >> 1;
  24.             Set<Long> set = new HashSet<>();
  25.             for (int i = mid; i <= n; i++)
  26.                 set.add(get(a1, i - mid + 1, i));
  27.             boolean flag = false;
  28.             for (int j = mid; j <= m; j++)
  29.                 if (set.contains(get(a2, j - mid + 1, j))) {
  30.                     flag = true;
  31.                     break;
  32.                 }
  33.             if (flag) l = mid;
  34.             else r = mid - 1;
  35.         }
  36.         return l;
  37.     }
  39.     long get(long[] a, int l, int r) {
  40.         return a[r] - (a[l - 1] * pow[r - l + 1]);
  41.     }
  42. }