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

Найдите подстроку длины n, которая повторяется максимальное количество раз в заданной строке.Максимально повторяющаяся подстрока размера 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) пространства решения?

источник

2017-02-11 Leo18

Хорошая проблема. Чашка чая, пока мы решим это для вас, сэр или мэм? Покажите, что вы пробовали, чтобы решить проблему самостоятельно. – Paul

Я отредактирую вопрос с тем, что я пробовал. – Leo18

Посмотрите на [этот вопрос] (http://stackoverflow.com/questions/38372159/longest-maximum-repeating-substring). Не решает ту же проблему, что и у вас, но она легко трансформируется. Или в качестве альтернативы это [статья википедии] (https://en.wikipedia.org/wiki/Longest_repeated_substring_problem) также предоставляет решение. – Paul

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

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

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

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

источник

2017-02-14 10:09:11 Gassa

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

ответ

Смежные вопросы