LeetCode 1062. 最长重复子串（二分查找）

示例 1：
输入："abcd"
输出：0
解释：没有重复子串。

示例 2：
输入："abbaba"
输出：2
解释：最长的重复子串为 "ab" 和 "ba"，每个出现 2 次。

示例 3：
输入："aabcaabdaab"
输出：3
解释：最长的重复子串为 "aab"，出现 3 次。

示例 4：
输入："aaaaa"
输出：4
解释：最长的重复子串为 "aaaa"，出现 2 次。
 
提示：
字符串 S 仅包含从 'a' 到 'z' 的小写英文字母。
1 <= S.length <= 1500

class Solution {
public:
    int longestRepeatingSubstring(string S) {
    	int l = 0, r = S.size()-1, len, maxlen;
    	while(l <= r)
    	{
    		len = l+((r-l)>>1);
    		if(haveRepeat(S, len))
    			maxlen = len, l = len+1;
    		else
    			r = len-1;
    	}
    	return maxlen;
    }
    bool haveRepeat(string& S, int len)
    {
    	unordered_set<string> set;
    	string sub;
    	for(int i = 0; i <= S.size()-len; i++)
    	{
    		sub = S.substr(i, len);
    		if(!set.count(sub))
    			set.insert(sub);
    		else
    			return true;//有重复的子串
    	}
    	return false;
    }
};