Longest Repeating Substring

题目(LeetCode #1062)

Given a string S, find out the length of the longest repeating substring(s). Return 0 if no repeating substring exists.

Example 1:

Input: “abcd”
Output: 0
Explanation: There is no repeating substring.

Example 2:

Input: “abbaba”
Output: 2
Explanation: The longest repeating substrings are “ab” and “ba”, each of which occurs twice.

Example 3:

Input: “aabcaabdaab”
Output: 3
Explanation: The longest repeating substring is “aab”, which occurs 3 times.

Example 4:

Input: “aaaaa”
Output: 4
Explanation: The longest repeating substring is “aaaa”, which occurs twice.

Note:

1. The string S consists of only lowercase English letters from 'a' - 'z'.
2. 1 <= S.length <= 1500

题解

若 S 中存在长度为 N 的重复字符串，则长度为 N - 1 的重复字符串也必然存在，故可用二分法猜最大长度的方法逼近实际结果。

class Solution {
    public int longestRepeatingSubstring(String s) {
        if (s == null || s.length() < 2) return 0;

        int l = 0, r= s.length() - 1;
        while (l < r) {
            int m = l + (r - l + 1) / 2;
            if (exist(s, m)) l = m;
            else r = m - 1;
        }

        return l;
    }

    private boolean exist(String s, int m) {
        /* 存储字符串的 hash 值, 节省空间 */
        Set<Integer> set = new HashSet<>();

        for (int i = 0; i <= s.length() - m; i++) {
            int j = i + m - 1;
            String sub = s.substring(i, j + 1);
            int hash = sub.hashCode();
            if (set.contains(hash)) return true;
            else set.add(hash);
        }

        return false;
    }
}