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

Question

找出给定字符串中重复次数最多的长度为 n 的子字符串。

输入:abbbabbbb#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)空间的方案做得更好？

Answer 1

对于长度为 L 和给定长度 k 的字符串(不要弄乱 n 和 m 问题有时会互换)，我们可以在 O(L) 中计算长度为 k 的所有子串的多项式哈希(有关此子问题的详细说明，请参阅 Wikipedia ).

现在，如果我们将散列值映射到它们出现的次数，我们将在 O(L) 中得到最频繁出现的值(使用具有高概率的 HashMap，或者在 O(L log L) 和 TreeMap。

之后，只取得到最频繁散列的子串作为答案。

---

此解决方案不考虑哈希冲突。这个想法只是为了减少应用程序的冲突概率(如果它太高，例如使用多个哈希)。如果应用程序要求我们绝对不会给出错误的答案，我们可以用另一种算法(例如 KMP)检查 O(L) 中的答案，然后用不同的算法重新运行整个解决方案哈希函数，只要答案被证明是错误的。