一、题目描述

给定字符串s，找出最长重复子串的长度，如果不存在重复子串就返回0。
示例：

输入：“abbaba”
输出：2

二、解题思路

步骤一：给出一个子串长度k交给步骤二进行判断。若输入字符串的总长度为n，可能存在的重复子串的长度一定在[0, n)范围内，可以采用二分方法查找子串长度。若已经判断出输入字符串存在长度为k的重复子串，接下来可以继续在[k+1, n)的子串长度范围内查看是否存在重复子串；若对于长度为k的子串无重复子串，则在[0, k)的子串长度范围内搜索。
步骤二：判断输入字符串是否存在长度为k的重复子串。在步骤一的二分框架下，判断每次指定的定子串长度k是否存在重复子串，搜索方法如下：利用长度为k的滑动窗口遍历字符串中所有长度为k的子串，用哈希集合记录得到的子串，判断是否存在重复子串。

三、代码实现

实现分为两部分，算法入口函数为longestRepeatingSubstring，内部采用二分框架，每次给出一个需要判断的子串长度mid，利用isRepeating函数实现搜索是否存在重复子串的功能，存在重复子串函数返回true，否则返回false。

class Solution {
public:
    bool isRepeating(string& s, int len){ //判断长度为len的子串是否重复
        unordered_set<string> st;
        for(int i = 0; i <= s.size()-len; ++i){
            string tmp = s.substr(i, len); //生成当前窗口中的子串
            if(st.count(tmp)) return true;
            st.insert(tmp);
        }
        return false;
    }
    int longestRepeatingSubstring(string s) {
        int n = s.size();
        // 二分框架
        int l = 0, r = n;
        while(l < r){
            int mid = l + (r - l) / 2;
            if(isRepeating(s, mid)){ //接下来在[mid+1, r)区间中搜索
                l = mid + 1;
            }else{                   //接下来在[l, mid)区间中搜索
                r = mid;
            }
        }
        return l - 1;
    }
};