В комментариях было большое обсуждение, я думаю, что лучше написать ответ, чтобы подвести итог. TL; DR Самая длинная подстрока, повторяющаяся по крайней мере k раз
Существует менее эффективный метод, но его действительно легче понять, чем суффиксные деревья: все, что вам нужно знать, - это полиномиальное хеширование и двоичный поиск.
1. Строка полинома га sh
Подробнее об этом можно прочитать здесь https://cp-algorithms.com/string/string-hashing.html. Ниже приведено краткое описание этой техники.
Допустим, у нас есть строка s, целые числа p и mod. Теперь мы можем определить функцию ha sh:
hash(s) = (ord(s[0])*p^(len(s)-1) + ord(s[1])*p^(len(s)-2) + ... + ord(s[len(s)-1])*p^0) % mod
, где ord - это функция, возвращающая целое число за символ (скажем, это ASCII-код символа). Полиномиальный га sh может быть легко вычислен для каждого префикса строки в O (len (s)) :
# h[i] is a hash of prefix of length i.
# For example s = "abacaba",
# h[0] = hash("") = 0
# h[1] = hash("a")
# h[2] = hash("ab")
# ...
# h[7] = hash("abacaba")
h[0] = 0
for i in 1..n:
h[i] = (h[i-1] * p + ord(s[i-1])) % mod
Также давайте предварительно вычислим p ^ 0% мод, p ^ 1% mod, ..., p ^ len (s)% mod в массиве pow:
# pow[i] is (p^i) % mod
pow[0] = 1
for i in 1..n:
pow[i] = (pow[i-1] * p) % mod
Используя массивы h и pow, мы можем легко вычислить га sh любой подстроки строки s:
# get_substring_hash returns hash(s[l] + s[l+1] + ... + s[r-1]).
def get_substring_hash(s, l, r):
value = h[r] - h[l]*pow[r-l] # line a
return (value%mod + mod) % mod # line b
Давайте разберемся, почему работает приведенный выше код.
h[r] = (ord(s[r-1])*p^0 + ord(s[r-2])*p^1 + ... + ord(s[l-1])*p^(r-l) + ord(s[l-2])*p^(r-l+1) + ...) % mod
h[l] = ( ord(s[l-1])*p^0 + ord(s[l-2])*p^1 + ...) % mod
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Как видите, нам нужна только ^^^ -part от h[r], поэтому мы должны избавиться от ~~~ -части. ~~~ -часть в h[r] p^(r-l) раз больше, чем в h[l], и этим объясняется линия a .
линия b является своего рода волхвами c при работе с % mod, value после строка a может быть отрицательной, поэтому value%mod + mod определенно делает положительным. В то же время, если value был положительным после строки , то value%mod + mod больше, чем mod, поэтому (value%mod + mod) % mod обязательно вернет значение в диапазоне 0, 1, ..., mod-1 .
Наконец, mod - это большое простое число, такое как 10 ^ 9 + 7 и value - небольшое число, но больше, чем любой возможный ASCII -код вроде 239 (читайте в статье, почему так).
Некоторые примечания:
- Хэши могут конфликтовать, потому что у нас есть только
mod возможных значений ха sh но количество строк бесконечно. Как с этим бороться читайте в статье. - Для выполнения таких операций, как
h[r] - h[l]*pow[r-l], может потребоваться использование 64-битных типов целых чисел.
2. Двоичный поиск
Просто прочитайте об этом в Википедии, там нет ничего конкретного c https://en.wikipedia.org/wiki/Binary_search_algorithm.
3. Самая длинная подстрока, повторяющая не менее k раз решение
Допустим, мы предварительно вычислили массивы h и pow. Давайте сделаем бинарный поиск, чтобы найти максимальную длину ans строки, чтобы в данной строке было k или более таких подстрок s.
Почему здесь работает бинарный поиск? Потому что если есть некоторая длина x, такая как * k или более равных подстрок в s длины x, то определенно k или более равных подстрок в s длины x-1 (просто удалите последнюю букву из наших совпадений).
Как будет работать бинарный поиск? Допустим, мы сейчас проверяем, есть ли k или более равных подстрок длины mid. Мы собираемся вычислить все хэши длины mid (используя get_substring_hash), и мы примем решение об изменении границ бинарного поиска, если есть k равных хэшей или нет.
Например: s = "abcabcdefgdefgdefgdefg", k = 3 . Ответ: "defgdefg" :
abcabcdefgdefgdefgdefg
^^^^^^^^ occurence 1
^^^^^^^^ occurence 2
^^^^^^^^ occurence 3
Итерации бинарного поиска:
l = 1, r = 22, mid = 11. No substring of length 11 satisfy.
l = 1, r = 10, mid = 5. There should be hash("defgd") be seen 3 times.
l = 5, r = 10, mid = 7. There should be hash("defgdef") be seen 3 times.
l = 7, r = 10, mid = 8. There should be hash("defgdefg") be seen 3 times.
l = 8, r = 10, mid = 9. No substring of length 9 satisfy.
l = 8, r = 8. That means answer is 8.
Как видите, сложность составляет O (n log n) : round (log n) бинарные итерации поиска и O (n) сложность на итерацию, если вы используете что-то вроде std::unordered_map, чтобы проверить, есть ли ха sh с > = k случаев или нет.
Я действительно надеюсь, что теперь все ясно.