😷1062 longest repeating substring

https://leetcode.com/problems/longest-repeating-substring/

class Solution {
    public int longestRepeatingSubstring(String S) {
        int n = S.length();
        int left = 0;
        int right = n;
        int L;
        while (left + 1 < right) {
            L = left + (right - left) / 2;
            if (search(L, n, S) != -1) {
                left = L;
            } else {
                right = L;
            }
        }
        if (search(right, n, S) != -1) {
            return right;
        }
        return left;
    }
    private int search(int L, int n, String S) {
        if (L == 0) {
            return 0;
        }
        Set<String> seen = new HashSet();
        String tmp;
        for (int start = 0;start < n - L + 1; start++) {
            tmp = S.substring(start, start + L);
            if (seen.contains(tmp)) return start;
            seen.add(tmp);
        }
        return -1;
    }
}

实在是不知道怎么评价。。。

我算是发现了，只要答案所在的区间有界且有序，就可以用binary search试出来， 这里可以用binary search是因为substring长度越长就越不可能repeat

同时找是不是有某个长度的substring在repeat没有好办法，只有遍历，取substring，不然就得用rabin karp

这道题代表了隐式binary search的经典形式，直接搜索答案区间，可以看作是一种对暴力枚举的优化