Строки – 2

Определение

Строка – набор символов. Индексация с 0. \(|s|\) – размер строки

Подстрока – набор последовательно расположенных символом некоторой строки. Подстроку можно однозначно задать: строкой, из которой она была взята, и двумя индексами (начала и конца). Пусть дана строка \(s\). Общий вид подстроки: \(\overline{s_i, s_{i + 1}, \dots, s_{j}}\). Как правило, в нашей нотации \(i\) – будет индексом начала подстроки, \(j\) – индексом конца подстроки (включительно)

Префикс строки – подстрока, которая начинается с начала строки, то есть \(i = 0\)

Суфикс строки – подстрока, которая заканчивается в конце строки, то есть \(j = |s| - 1\)

Мотивация

Пришла пора рассмотреть простые алгоритмы на строках, которые позволяют эффективно по времени решать типовы задачи, к которым относятся:

  • сравнение подстрок

  • проверка подстроки на палиндром

  • нахождение всех подпалиндромов (подстрок, которые являются палиндромами)

  • поиск всех вхождение строки в текст

Наивная асимптотика некоторых операций

Перебор всех подстрок имеет асимптотическую сложность в \({\cal{O}}(n^2)\). Обоснуем это.

Каждая подстока задается двумя индексами, каждый из которых \(\in [0; |s| - 1]\), то есть может принимать \(|s|\) значений. Количество вариантов выбрать 2 различных элемента из набора – это количество сочетаний. Если подстрока состоит из одного символа, то индекса совпадают, и это нужно отдельно учесть. Пусть \(|s| = n\)

Тогда: \(n + C_{n}^{2} = n + \frac{n!}{2! \cdot (n - 2)!} = n + \frac{n (n - 1)}{2} = {\cal{O}}(n^2)\) – квадратичная асимптотика

Сравнение строк обладает линейной сложностью. Действительно, нужно один раз сравнить все символы, чтобы в этом убедиться.

Существуют ли более оптимальные алгоритмы, например, для поиска подстроки? Оказывается, что существуют и обладают линейной сложностью, но перед их применением необходимо ввести ряд концепций.

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

Постановка задачи

Формально, префикс-функция от строки \(s\) и индекса \(i\) – длина наибольшего префикса строки, который также является суффиксом \(i\)-того префикса.

Давайте разбираться, что это означает.

Хотим посчитать \(\pi(i)\) (здесь и далее опускаем один из аргументов префикс-функции – строку, по которой она строится. Считаем, что рассматривается строка \(s\)). Для этого рассматриваем \(i\)-тый префикс: \(s_0 s_1 \dots s_i\) и отвечаем на вопрос: какое наибольшее количество первых символов здесь можно взять (префикс), чтобы они совпадали с символами в конце (суффикс).

Теперь на примерах:

Строка \(s\) a a t a a t a a
\(\pi[i]\) 0 1 0 1 2 3 4 5

Покажем расчет \(\pi[7] = 5\), фигурными скобка показаны равные префикс и суффикс, которые были подсчитаны префикс-функцией

\[ \rlap{ \underbrace{ \phantom{aataa} } } aat \rlap{ \overbrace{ \phantom{aataa} } } aataa \]

Наивный подсчет за \({\cal{O}}(n^3)\)

Отлично, как же посчитать префикс-функцию? Наивный алгоритм заключается в подсчете \(n\) значений: для каждого перебираем \(O(n)\) префиксов и за \(O(n)\) сравнением с суффиксом той же длины. Итоговая асимптотическая сложность – \({\cal{O}}(n^3)\). Но можно лучше, если хитро использовавать значения префикс-функции, которые были посчитаны до этого.

Оптимальный алгоритм за \({\cal{O}}(n)\)

Введем понятие “ожидаемого символа” – это такой, который продлевает известный нам суффикс. Например, в примере выше последний символ именно a, он продолжает совпадение суффикса-префикса aata до aataa. Тогда мы можем сразу посчитать значение префикс-функции: \(\pi[7] = \pi[6] + 1 = 4 + 1 = 5\). Сразу отметим, что \(\pi[i] \le \pi[i - 1] + 1\), то есть значение не может возрастать более, чем на единицу

Промежуточный итог рассуждений – если символ совпал с ожидаемым для совпадающего суффикса размера \(p\), то значение префикс функции будет равно \(p + 1\). Тогда наша задача найти такой суффикс, и здесь нам будет помогать, что суффикс совпадает с префиксом, а для него на прошлых шагах мы уже считали значение префикс-фукнции.

Итоговый алгоритм в формате псевдокода:

s = "..."
p = [0, 0, ..., 0]
for i: 1-> n
    k = p[i - 1]
    while s[k] != s[i] and k > 0: # пока фактический символ (s[i]) не совпал с ожидаемым для текущего префикса (s[k])
        k = p[k - 1]
    if s[k] == s[i]: # если мы все же нашли совпадение, то тогда считаем
        p[i] = k + 1 # длина найденного префикс + 1
    # а иначе значение префикс-функции -- ноль

Заметим, что в среднем цикл while выполняется за \(O(1)\), поэтому сложность подсчета префикс-функции – это \({\cal{O}}(n)\), то есть амортизированная линейная сложность. Амортизированная сложность у нас встречалась в курсе, когда мы рассматривали, как происходит добавление элемента в конец вектора

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

Это алгоритм с помощью подсчета префикс-функции позволяется найти все вхождение строки \(s\) в текст \(t\) за \({\cal{O}}(|t|)\).

  • Составим новую строку, сконкатенировав данные и разделитель: \(s'' = s + "*" + t\). В качестве разделителя используется символ, который не встречается ни в строке, ни в тексте.

  • По составленной строке считается префикс-функция. На самом деле можно даже считать только префикс-функцию для текста, заполним начальные значения нулями.

  • \(\pi[i] = |s|\) означается, что на индексе \(i\) заканчивается очередное вхождение строки \(s\) в текст \(t\). Действительно, это же означает, что слева от позиции \(i\) ровно \(|s|\) символов совпадают с префиксом, который и равен нашей искомой строке.

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

При постановке задачи мы хотели находить все вхождения строки в текст, значит, и индексы начал вхождений логично выводить именно для текста, а не новой собранной строки. Несложной арифметикой мы получаем, что если \(\pi[i] = |s|\), то \(i - 2|s|\) – индекса начала этого вхождения.