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

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

    示例 1：

    输入：s = “banana”
    输出：”ana”
    示例 2：

    输入：s = “abcd”
    输出：””

    提示：

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

    写了个kmp超时了

    1. class Solution {
    2.     String res = "";
    3.     int[] ne = new int[30010];
    4.     public String longestDupSubstring(String s) {
    5.         int n = s.length();
    6.         for (int len = 1; len <= n-1; ++len) 
    7.             for (int i = 0; len + i - 1 < n; ++i) {
    8.                 int j = len + i - 1;
    9.                 String ss = s.substring(i,j+1);
    10.                 if (matching(ss,s)) break;
    11.             }
    12.         return res;
    13.     }
    14.     public boolean matching(String a, String b) {
    15.         int n = a.length(), m = b.length();
    16.         a = " " + a;
    17.         b = " " + b;
    18.         int count = 0;
    19.         //求next
    20.         for (int i = 2, j = 0; i <= n; ++i) {
    21.             while (j > 0 && a.charAt(i) != a.charAt(j+1)) j = ne[j];
    22.             if (a.charAt(i) == a.charAt(j+1)) j++;
    23.             ne[i] = j;
    24.         }
    25.         //匹配过程
    26.         for (int i = 1, j = 0; i <= m; ++i) {
    27.             while (j > 0 && b.charAt(i) != a.charAt(j+1)) j = ne[j];
    28.             if (b.charAt(i) == a.charAt(j+1)) j++;
    29.             if (j == n) {
    30.                 count++;
    31.                 if (count >= 2) break;
    32.                 j = ne[j];
    33.             }
    34.         }
    35.         if (count >= 2) {
    36.             res = a.trim();
    37.             return true;
    38.         }
    39.         return false;
    40.     }
    41. }

    字符串哈希+二分

    1. class Solution {
    2.     /**
    3.     本题采用字符串哈希+哈希集合的方式处理判断是否有重复的子串
    4.     而对于寻找最长长度的子串外面可以使用二分，因为答案具有二段性
    5.         小于等于最大长度的子串存在
    6.         而大于最大长度的子串不存在
    7.      */
    8.     long[] h,p;
    9.     public String longestDupSubstring(String s) {
    10.         int n = s.length();
    11.         //P一般取131或13331，取模Q一般是2^64，所以我们只用long就行，溢出就相当于取模了
    12.         int P = 131;
    13.         String res = "";
    14.         //h数组表示s的前缀和哈希，p数组时表示P进制
    15.         h = new long[n+10]; 
    16.         p = new long[n+10];
    17.         p[0] = 1;
    18.         for (int i = 0; i < n; ++i) {
    19.             p[i+1] = p[i] * P;            //预处理p数组方便后面求子串哈希值
    20.             h[i+1] = h[i] * P + s.charAt(i); //理解为将字符串转换P进制为前缀和数组
    21.         }
    22.         int l = 0, r = n-1;
    23.         while (l < r) {
    24.             int mid = l + r + 1 >> 1;
    25.             String ss = check(s,mid);
    26.             if (ss.length() != 0) l = mid;
    27.             else r = mid - 1;
    28.             res = res.length() < ss.length() ? ss : res;
    29.         }
    30.         return res;
    31.     }
    32.     public String check(String s, int len) {
    33.         int n = s.length();
    34.         String res = "";
    35.         Set<Long> set = new HashSet<>();
    36.         for (int i = 0; len + i - 1 < n; ++i) {
    37.             int j = len + i - 1;
    38.             //h[j]代表1~j的字符串哈希值，h[i]代表1~i的字符串哈希值
    39.             //因为我们是看成P进制所以我们先要把h[i] * p[j-i+1] 转换为跟h[j]
    40.             //同样的位数，再相减即为哈希值
    41.             long hash = h[j+1] - h[i] * p[j-i+1];
    42.             if (set.contains(hash)) {
    43.                 res = s.substring(i,j+1);
    44.                 return res;
    45.             }
    46.             set.add(hash);
    47.         }
    48.         return "";
    49.     }
    50. }