Самая длинная подстрока, повторяющаяся не менее k раз

Допустим, у нас есть строка s, целые числа p и mod. Теперь мы можем определить хэш-функцию:

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-код символа). Полиномиальный хэш можно легко вычислить для каждого префикса строки в 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 % mod, 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, мы можем легко вычислить хэш любой подстроки строки 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
        ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Как видите, нам нужна только ^^^-часть из h[r], поэтому мы должны избавиться от ~~~-части. ~~~-часть в h[r] p^(r-l) раз больше, чем в h[l], и это объясняет строку a.

Строка b — своего рода магия при работе с % mod, value после строки a может быть отрицательной, поэтому value%mod + mod определенно дает положительное значение. В то же время, если value было положительным после строки a, value%mod + mod больше, чем mod, поэтому (value%mod + mod) % mod обязательно вернет значение в диапазоне 0, 1, ..., mod-1 .

Наконец, mod — это большое простое число, такое как 10^9+7, а value — это небольшое число, но оно больше любого возможного ASCII-кода, такого как 239 (читайте в статье, почему так).

Некоторые примечания:

• Хеши могут конфликтовать, потому что у нас есть только mod возможных значений хеша, а количество строк бесконечно. Как с этим бороться читайте в статье.
• Выполнение таких операций, как h[r] - h[l]*pow[r-l], может потребовать использования 64-битных типов целых чисел.

<сильный>2. Бинарный поиск

<сильный>3. Самая длинная подстрока, повторяющаяся как минимум k раз

Допустим, мы предварительно вычислили массивы h и pow. Выполним бинарный поиск, чтобы найти максимальную длину строки ans, такую, чтобы в заданной строке s было k или более таких подстрок.

Почему здесь работает бинарный поиск? Потому что если есть какая-то длина x, например, k или более равных подстрок в s длины x, то в s длины x-1 определенно есть k или более равных подстрок (просто удалите последнюю букву из наших совпадений).

Как будет работать бинарный поиск? Допустим, мы сейчас проверяем, есть ли 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, чтобы проверить, есть ли хэш с >= k вхождениями или нет.

Очень надеюсь, что теперь все ясно.