Суффиксы, префиксы и подстроки

Суффиксы, префиксы и подстроки

Оглавление

• Z-функция (Z-function)
  • [Нахождение самой длинной грани в строке]
  • [Нахождение периода строки]
  • [Задача о неточном поиске]
  • [Число различных подстрок в строке]
  • [Сжатие строки]
  • [Палиндромные префиксы]
• Префикс-функция
  • [Подсчет числа вхождений каждого префикса]
  • [Количество различных подстрок в строке]
  • [Сжатие строки]
  • [Построение автомата по префикс-функции]
• Алгоритм Кнута-Морриса-Пратта
• [Переход от Z-функции к префикс-функции и обратно]
• Суффиксный массив (Suffix-array)
  • [Число различных подстрок]
  • [Наибольшая общая подстрока]
• Алгоритм Манакера
  • Наивный алгоритм
• Хэш-функция
  • Количество различных подстрок
  • Поиск подстроки в строке
  • Сравнение строк
  • Палиндромность подстроки
  • Количество палиндромов

Теория

2 Суфффиксы, префиксы и подстроки

Z - функция

Z-функция от строки s определяется как массив z, такой, что z_i равно длине максимальной подстроки, начинающейся с i-й позиции, которая равна префиксу s.

Пример:

abacabadava
00103010101
a = 0 (первый элемент всегда равен 0 или длине строки)
ab = 0 (так как b не совпадает с префиксом)
aba = 1 (так как a совпадает с префиксом)
abac = 0
abaca = 3 (так как aba=aba)
и т.д.

Реализация за O(n)

def get_z(s):
    n = len(s)
    z = [0] * n
    l = r = 0

    for i in range(1, n):
        if r >= i:
            z[i] = min(z[i - l], r - i + 1)

        while z[i] + i < n and s[z[i]] == s[z[i] + i]:
            z[i] += 1

        if z[i] + i - 1 > r:
            l = i
            r = z[i] + i - 1
    return z

Префикс - функция

Префикс-функцией от строки s называется массив p где p_i равно длине самого большого префикса строки s₀s₁s₂...s_n.

Пример:

abacabadava
00101230101

a = 0
ab = 0
aba = 1, так как префикс и суффикс совпадают a=a
abac = 0
abaca = 1
abacab = 2, ab=ab
abacaba = 3, aba=aba
abacabad = 0
abacabada = 1
abacabadav = 0
abacabadava = 1

Реализация за O(n)

def prefix_function(s):
    n = len(s)
    p = [0] * n
    for i in range(1, n):
        k = p[i-1]
        while (k > 0 and s[k] != s[i]):
            k = p[k - 1]
        if s[i] == s[k]:
            k += 1
        p[i] = k
    return p

print(*prefix_function(input()))

Алгоритм Кнута-Морриса-Пратта

Дан текст t и строка s. В нем требуется найти и вывести позиции всех вхождений строки s в текст t.

n - длина s; m - длина t.

Алгоритм:

1. Образуем строку s + $ + t;
2. Посчитаем для этой строки префикс-функцию или Z-функцию;
3. Рассмотрим её значения для всех позиций кроме n+1;
4. В тех местах где значения массива равны n - встретилось вхождение строки s.

Алгоритм требует O(n) памяти и O(n+m) времени.

Реализация

t = input()
s = input()

n = len(s)
m = len(t)

z = get_z(s+"$"+t)

res = []
for i in range(n+1,n+m+1):
    if z[i] == n:
        res.append(i-n)
print(len(res))
print(*res)

Суффиксный массив

Алгоритм Манакера

Задача:

Пусть дана строка s.
Требуется найти количество подстрок s, являющихся палиндромами.
Более формально: все такие пары (i,j), что s[i:j] - палиндром.

Легко увидеть, что в худшем случае таких подстрок будет n². Значит пусть d₁[i] - количество палиндромов нечетной длины с центром в позиции i, а d₂[i] - аналогичная величина для палиндромов чётной длины. Вычислим значения.

Наивный алгоритм

Рассмотрим сначала задачу поиска палиндромов нечётной длины. Центром строки нечётной длины назовём символ под индексом:

center = len(t) // 2

Для каждой позиции в строке s найдем длину наибольшего палиндрома с центром в этой позиции. Очевидно, что если строка t является палиндромом, то строка полученная вычеркиванием первого и последнего символа из t также является палиндромом, поэтому длину палиндрома можно искать бинарным поиском. Проверить совпадение левой и правой половины можно выполнить за O(1), используя метод хеширования.

Для палиндромов чётной длины алгоритм такой же. Центр строки чётной длины — некий мнимый элемент между center и center+1. Только требуется проверять вторую строку со сдвигом на единицу. Следует заметить, что мы не посчитаем никакой палиндром дважды из-за четности-нечетности длин палиндромов.

Реализация алгоритма Манакера

Будем поддерживать границы самого правого из найденных палиндромов - [l,r]. Итак, пусть мы хотим вычислить d₁[i] - т.е. длину наибольшего палиндрома с центром в позиции i. При этом все возможные значения в массиве d уже посчитаны.

Всего возможно 2 случая:

1. i > r, т.е. текущая позиция не совпадает в границы самого правого из найденных палиндромов. Тогда просто запустим наивный алгоритм для позиции i.
2. i ≤ r. Тогда попробуем воспользоваться значениями, посчитанными ранее. Отразим нашу текущую позицию внутри палиндрома [l;r] : j =(r-i) + l. Поскольку i и j симметричные позиции, то если d₁[j]=k, мы можем утверждать, что и d₁[i] = k. Это объясняется тем, что палиндром симметричен относительно своей центральной позиции - то есть имеем некоторый палиндром длины k с центром в позиции l ≤ i ≤ r, то в позиции j, симметричной i относительно отрезка [l;r] тоже может находиться палиндром длины k.

Фигурными скобками обозначены равные подстроки. Однако стоит не забыть про один граничный случай: Что будет, если i + d₁[j] - 1 выходит за границы самого правого палиндрома? Так как информации о том, что происходит за границами этого палиндрома у нас нет (а значит мы не можем утверждать, что симметрия сохраняется), то необходимо ограничить значение d₁[i] следующим образом: d₁[i] = min(r-i, d₁[j]). После этого запустим наивный алгоритм, который будет увеличивать значение d₁[i], пока это возможно.

После каждого шага важно не забывать обновлять значения [l,r].

Заметим, что массив d₂

Хэш-функция

Хэш — это какая-то функция, сопоставляющая объектам какого-то множества числовые значения из ограниченного промежутка.

Свойства хорошей хэш-функции:

1. Быстро считается за линейное время, зависящее от размера объекта;
2. Имеет не очень большиее значения, помещающиеся в 2⁶ бит;
3. Детерменированно-случайная - если хэш может принимать n различных значений, то вероятность того, что хэши совпадут - 1/n.

Сюрьективные хэши - обычно хэш функция не является взаимно однозначной: одному хэшу могут соответствовать много объектов.

Для некоторых задач удобнее работать с хэшами, чем с самими объектами. Пусть даны n строк длины m, и нас просят q раз проверить произвольные две на равенство. Вместо взаимной проверки O(n*m*q) мы можем посчитать хэши всех строк, сохранить, и во время ответа на запрос сравнивать два числа.

Применения хэш-функции:

• Чек-суммы
• Хэш-таблица
• Мемоизация
• Проверка на изоморфизм
• Криптография
• Поиск в многомерных пространствах

Хэшируемые объекты могут быть самыми разными: строки, изображения, графы, шахматные позиции, просто битовые файлы.

Полиномиальное хэширование

Будем считать, что строка - последовательность чисел от 1 до m (размер алфавита). В языках программирования любой символ - это число, значит:

x = ord(letter) - ord("a") + 1

Полиномиальный хэш строки

h_f = (s₀ + s₁k + s₂k² + ... + s_nkⁿ) mod p

Здесь k - произвольное число больше размера алфавита, а p достаточно большой модуль, вообще говоря, не обязательно простой.

Его можно посчитать за линейное время поддерживая переменную, равную нужной в данный момент степени k:

k = 31
mod =10**9 + 7
s = "abacabadaba"
h = 0
m = 1

for letter in s:
    x = ord(letter) - ord("a") + 1
    h = (h + m * x) % mod
    m = (m * k) % mod

print(h)

Обратный полиномиальный хэш

h_b = (s₀kⁿ + s₁k^n-1 + s₂k^n-2 + ... + s_n) mod p

for letter in s:
    x = ord(letter) - ord("a") + 1
    h = (h * k + x) % mod
print(h)

Применение хэширования

Используя тот факт, что хэш это значение многочлена, можно быстро пересчитывать хэш от результата выполнения многих строковых операций.

Например, если нужно посчитать хэш от конкатенации строк a и b (s = a+b), то можно просто хэш b домножить на k^|a| и сложить с хэшом a:

h(ab) = h(a) + k^|a| * h(b)

a = "abacaba"
b = "daba"
h_ab = hash(a) + k**len(a) * hash(b)

Удаление префикса строки:

h(b) = (h(ab)-h(a))/k^|a|

h_b = (hash(ab)-hash(a))/(k**len(a))

Удаление суффикса:

h(a) = h(ab)-k^|a|*h(b)

h_a = hash(ab) - k**len(a) * hash(b)

В задачах часто бывает потребность в домножении на k в какой-то степени, поэтому можно их просчитать заранее:

max_n = 10**5+5

p = [0]*max_n
p[0] = 1

for i in range(1,n):
    p[i] = (p[i-1]*k) % mod

Пусть нам надо отвечать на запросы проверки на равенство произвольных подстрок одной большой строки. Подсчитаем значение хэш-функции для каждого префикса:

h = [0] * max_n
h[0] = 0 # h[k] - хэш префикса длины k
# s - последовательность int-ов
for i in range(n):
    h[i+1] = (h[i]+p[i]*s[i]) % mod

Функция считающая хэш на произвольном подотрезке:

h(s[l:r]) = (h_r - h_l) / k_l

def hash_substring1(l,r):
    return (hash(r) - hash(l))/(k**l)

Вместо приведения к нулевой степени приведём многочлен к какой-нибудь достаточно большой — например, к n-ной. Так проще — нужно будет домножать, а не делить.

def hash_substring2(l,r):
    return (h[r+1] - h[l]) * p[n-1] % mod

Теперь мы можем просто вызывать эту функцию от двух отрезков и сравнивать числовое значение, отвечая на запрос за O(n).

Выбор констант

Практическое правило: если вам нужно хранить n различных хэшей, то безопасный модуль — это число порядка 10 * n².

Не всегда такой можно выбрать один — если он будет слишком большой, будут происходить переполнения. Вместо этого можно брать два или даже три модуля и считать много хэшей параллельно.

Так же можно брать модуль 2⁶⁴. У него есть несколько преимуществ:

• Он большой - второй модуль точно не понадобится
• Хэширование происходит быстрее

Однако есть тест против такого модуля. Нужно использовать аккуратно.

При выборе k ограничения не такие серьезные:

• Она должна быть чуть больше словаря - иначе можно изменить две соседние буквы и получить коллизию.
• Она должна быть взаимно проста с модулем - иначе в какой-то момент может все занулиться.

Количество различных подстрок

Подсчитаем хэши всех подстрок за O(n²) и добавим их в set. Ответ: len(set)

Поиск подстроки в строке

Можно посчитать хэши от шаблона (строки, которую ищем) и пройтись «окном» размера шаблона по тексту, поддерживая хэш текущей подстроки. Если хэш какой-то из этих подстрок совпал с хэшом шаблона, то мы нашли нужную подстроку. Это называется алгоритмом Рабина-Карпа.

Сравнение строк

У любых двух строк есть какой-то общий префикс (возможно, пустой). Сделаем бинпоиск по его длине, а дальше сравним два символа, идущие за ним.

Палиндромность строки

Можно посчитать два массива — обратные хэши и прямые. Проверка на палиндром будет заключаться в сравнении значений hash_substring() на первом массиве и на втором.

Количество палиндромов

Можно перебрать центр палиндрома, а для каждого центра — бинпоиском его размер. Проверять подстроку на палиндромность мы уже умеем. Как и всегда в задачах на палиндромы, случаи четных и нечетных палиндромов нужно обрабатывать отдельно.