最长重复子串

class Solution { long mod = (long)Math.pow(2, 37) - 1; long a = 26; int nums[]; int n; public String longestDupSubstring(String S) { nums = new int [S.length()]; for (int i = 0; i < S.length(); i ++) { nums[i] = S.charAt(i) - 'a'; } this.n = S.length(); int left = 1; int right = n; while (left != right) { int mid = left + (right - left) / 2; if (search(mid) != -1) left = mid + 1; else right = mid; } int begin = search(left - 1); if (begin != -1) return S.substring(begin, begin + left - 1); return ""; } public int search(int length) { long cur = 0; for (int i = 0; i < length; i ++) { cur = (cur * a + nums[i]) % mod; } long aL = 1; for (int i = 0; i < length; i++) { aL = (aL * a ) % mod; } HashSet<Long> hs = new HashSet<>(); hs.add(cur); for (int i = 1; i <= n - length; i ++) { cur = (cur * a - aL * nums[i - 1] % mod + mod) % mod; cur = (cur + nums[i + length - 1]) % mod; if (hs.contains(cur)) return i; hs.add(cur); } return -1; } }