string - 大小为n的最大重复子串

查找长度n的子串，它在给定字符串中重复最大次数。
输入：abbbbbb#2
输出：BB
我的解决方案：

public static String mrs(String s, int m) {
    int n  = s.length();
    String[] suffixes = new String[n-m+1];
    for (int i = 0; i < n-m+1; i++) {
        suffixes[i] = s.substring(i, i+m);
    }
    Arrays.sort(suffixes);
    String ans = "", tmp=suffixes[0].substring(0,m);
    int cnt = 1, max=0;
    for (int i = 0; i < n-m; i++) {
        if (suffixes[i].equals(suffixes[i+1])){
            cnt++;
        }else{
            if(cnt>max){
                max = cnt;
                ans =tmp;
            }
            cnt=0;
            tmp = suffixes[i];
        }
    }
    return ans;
}

它能比上述O（nm）时间和O（n）空间溶液做得更好吗？

最佳答案

对于长度L的字符串和给定长度k（不要弄乱问题有时交换的n和m），我们可以计算k中所有长度O(L)的子字符串的多项式散列（有关此子问题的一些详细说明，请参见Wikipedia）。
现在，如果我们将散列值映射到它们出现的次数，我们将得到在O(L)中出现频率最高的值（使用具有高概率的散列映射，或使用treemap在O(L log L)中）。
然后，取得到最频繁散列的子串作为答案。
此解决方案不考虑哈希冲突。
这样做的目的只是减少应用程序发生冲突的可能性（例如，如果冲突的可能性太高，就使用多个散列）。
如果应用程序要求我们绝对不要给出错误的答案，我们可以使用另一个算法（例如KMP）检查O(L)中的答案，并使用不同的散列函数重新运行整个解决方案，只要答案是错误的。