Максимально повторяющаяся подстрока размера n

Question

Найдите подстроку длины n, которая повторяется максимальное количество раз в заданной строке.

Вход: abbbabbbb # 2
Выход: бб

Мое решение:

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 (нм) времени и O (N) пространства решения?

Answer 1

Для строки длины L и заданной длины k (не связываться с n и m которых вопрос переставляет в разы), мы можем вычислить полиномиальные хэши всех подстрок длины k в O(L) (см Wikipedia для некоторых разработка этой подзадачи).

Теперь, если мы сопоставляем значения хэша с количеством раз, которое они происходят, мы получаем значение, которое чаще всего встречается в O(L) (с высокой вероятностью HashMap или в O(L log L) с TreeMap).

После этого просто возьмите подстроку, которая получила самый частый хэш в качестве ответа.

---

Это решение не учитывает хеш-коллизии. Идея состоит в том, чтобы просто уменьшить вероятность возникновения коллизий для приложения (если оно слишком велико, используйте, например, несколько хэшей). Если приложение требует, чтобы мы абсолютно никогда не давали неправильного ответа, мы можем проверить ответ в O(L) с другим алгоритмом (например, KMP) и повторно запустить целое решение с другой функцией хеширования, если получится ответ ошибаться.