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

Задача поиска подстроки одна из достаточно распространённых в информатике. Строкой называют последовательность символов (в произвольном порядке) взятых из заданного алфавита. Так например, алфавитом могут быть цифры {0, 1} из которых можно составлять неограниченную по длине цепочку символов, например, 0110100110 или 0. Понятие алфавита и другие раскрываются в теории формальных языков.

В рамках этой статьи рассмотрены задачи нахождения одной строки в другой. Результатом поиска могут быть как простой ответ «да / нет» на вопрос «содержит ли данная строка представленный образец», так и информация о точном месте начала (или начал, если их несколько) совпадения подстроки с образцом. Назовём образцом искомую строку, а подстрокой — массив $S(i, j)$ для индексов $i, j$ таких что $0 \leq i \leq j \leq N$ , где $N$ — длина строки, а $S$ — сама строка. Также введём образец как $P$ .

Простой (наивный) поиск

Суть алгоритма простого поиска состоит в последовательном переборе с последующим сравнением символов строки и образца. Для этого достаточно выполнить следующий алгоритм:

  for i = 0 to S.length do:
    for j = 0 to P.length do: 
      if S[i + j] != P[j] then break
    end for
    if j == P.length then return i
  end for
  return -1

Переменная i отвечает за сдвиг образца на один символ на каждой итерации. Внутренний цикл проверяет совпадение символа строки с индексом i + j и символа образца с индексом j. Если символы не совпадают, тогда внутренний цикл прекращает работу. Оговоримся, что если алгоритм отрабатывает все итерации, то переменная цикла будет равна значению правой границы указанного как N. В таком случае, если длина образца и переменной равны, то это будет означать, что внутренний цикл не нашёл разных символов, а значит подстрока найдена, а индексом начала подстроки является переменная i. В противном случае внешний цикл продолжает работу.

Здесь намеренно не приводится ограничений на правую границу внешнего цикла, т.к. сути алгоритма это не меняет. В общем легко посчитать, что сложность такого поиска будет $O(N * M)$ , где $N$ — длина строки $S$ , а $M$ — образца $P$ .

Алгоритм Рабина — Карпа

Этот алгоритм старается уменьшить количество проверок во внутреннем цикле простого поиска за счёт использования хэш-функции.

Понятие хэш-функции

Хэш-функция в данном случае преобразовывает исходную строку в числовое значение. Само преобразование называется хэшированием и в общем может выполняться не только для строк, но и для произвольного массива данных, а выходным значением является битовый массив заданной длины. Рассмотрим эти определения на простых примерах, где задано множество $K$ чисел для которых нужно посчитать хэш-функцию в множество $R$ . Тогда нам нужна функция $hash(k)$ , значение которой будет принадлежать множеству $R$ .

Например, у нас есть множество целых чисел от 0 до 1 000 000 и ограничение на значение хэш-функции в 10 битов. 10 битов это $2^{10} = 1024$ доступных значений функции. Существуют различные способы написать такую функцию, например:

методом деления, когда входное число делится на количество доступных значений хэш-функции, а результатом является остаток от такого деления: $hash(k) = k \mod r$ ;
метод середины квадрата умножает входное число само на себя, а из его середины берётся необходимое количество знаков;
метод умножения имеет вид $hash(k)=\left[r\left\lfloor {\frac {A}{w}}*k\right\rfloor \right]$ , где $w$ — количество символов представимых машинным словом (для 32-битной системы это будет $2^{32} = 4294967296$ ), а $A$ — взаимно простое число к $w$ .

При любой функции могут случаться коллизии. Коллизиями называется ситуация, когда разные элементы множества $K$ отображаются в один элемент множества $R$ . Например, для примера в методе деления такое происходит при $k = \{1, 1025, 2049,...\}$ . Если коллизии не случаются, то такое хэширование называют идеальным хэшированием.

Также существуют хэш-таблицы, которые являются ещё одним способом создания словаря (англ. map). Они используют разные стратегии для разрешения коллизий при сохранении пары ключ-значения в таблицу, например, метод цепочек или метод открытой адресации.

Для работы алгоритма необходимо написать хэш-функцию для заданной строки. Если пронумеровать символы алфавита из которых состоит строка, то можно написать тривиальный скользящий хэш, представляющий из себя сумму индексов каждого символа. Например, когда задан алфавит {A, B, C, D}, а символы имеют индексы от 1 до 4, то для строки ACDDAB будем иметь, что 1 + 3 + 4 + 4 + 1 + 2 = 15.

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

PH = hash(P)
SH = hash(S(0, P.length))
for i = 0 to S.length do
  if PH == SH and S(i, i + P.length) == P then
    return i
  end if
  SH = SH - S[i] + S[i + P.length]
end for
return -1

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

Алгоритм Бойера — Мура

Идея этого алгоритма заключается в том, что строки можно сравнивать с конца. Это позволит пропускать не 1 символ как в наивном алгоритме, но зачастую сразу всю строку. Это возможно, поскольку в тот момент, когда обнаруживается несовпадающий символ между строкой и образцом, то образец необходимо сдвинуть вправо на столько символов, чтобы несовпадающий символ строки теперь совпал с символом образца. Если такого символа в образце нет, то строка сдвигается полностью.

Рассмотрим пример:

ровкдткотор
кот********

Начиная проверку с конца к началу определяем, что не совпадают символы «в» и «т». Сдвиг, величина шага которого зависит от таблицы, описанную позже, в этом случае будет равен 3:

ровкдткотор
***кот*****

Снова проверяем с конца: после совпадения «т» в обеих строках не совпадают «д» и «о». Снова сдвигаем, шаг в этом случае равен 3:

ровкдткотор
******кот**

В данном примере все символы совпадают, поэтому алгоритм останавливается. Теперь определим, каким образом определяется величина шага для каждого символа. Поскольку суть алгоритма в том, чтобы при несовпадении символа мы двигали образец вправо до тех пор, пока этот символ не совпадёт с символом образца:

персональные данные
данные************* -> не совпал "н" (не совпал в первом символе, индекс 5), сдвигаем на 5 - 3 = 2 (3 по таблице)
**данные*********** -> не совпал "л", сдвигаем на 6, т.к. символа нет в таблице
********данные***** -> не совпал "д" (не совпал в первом символе индекс 5), сдвигаем на 5 - 0 = 5 (0 по таблице)
*************данные -> совпали

Для составления таблицы используется следующее правило: значение для символа равно максимальному индексу этого элемента в образце (исключая последний символ, для него и всех других значение равно количеству символов в образце). Так для строки «данные» это будет:

д	а	н	ы	*
0	1	3	4	6

Тогда величина сдвига при сравнении справа налево и при не совпадении символа на j-ой позиции, где сам символ $c = S[j]$ , будет равна $i = j - Table[c]$ . Приведём алгоритм с приведённой эвристикой, называемой эвристикой стоп-символа:

table = create map
for i = 0 to P.length - 1 do
  table[P[i]] = i
end for

for i = 0 to S.length do #NEXT
  for j = P.length - 1 down to 0 do
    if P[j] != S[j + i] then
      step = j - table[S[j + i]]
      i = i + step
      go to #NEXT
    end if
  end for
  return i
end for
return -1

Эффективность поиска в таком алгоритме достигает $O(N + M)$

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

Последний из рассматриваемых алгоритмов и являющимся самым эффективным, т.к. работает за линейное время. Основой алгоритма является определение префикс-функции. Префикс-функция $\pi (S,i)$ вычисляет длину наибольшего собственного (т.е. не равного самой подстроке) префикса совпадающего с суффиксом этой подстроки. Так, для строки котокот префикс «кот» совпадает с суффиксом и длина его равна 3.

Наивный алгоритм подсчёта префикс-функции для произвольной строки $S$ при всех значениях $1\leqslant i\leqslant \left|S\right|$ (при этом $\pi (S,0) = 0$ ) занимает квадратичное время. Для более эффективного расчёта нужно отметить, что при добавлении нового символа подстроки $i + 1$ при $\pi (S, i) = k$ у нас может получится, что $S[i + 1] = S[k + 1]$ , т.е. увеличенный суффикс совпадает с префиксом. Это означает, что в этом случае можно сказать, что $\pi (S, i + 1) = k + 1$ . Если они не совпадают, то мы пробуем посмотреть на меньший суффикс. Поскольку $\pi (S, k)$ к этому моменту уже подсчитано и мы знаем для него префикс, то полагаем, что $k = \pi (S, k)$ и снова проверяем условие $S[i + 1] = S[k + 1]$ . Если в какой-то момент $k = 0$ , то полагаем, что $\pi (S, i + 1) = 0$ .

Таким образом задача сводится к заполнению таблицы вида:

i	0	1	…	N
π	0	*	…	*

Для решения задачи поиска подстроки достаточно склеить образец и строку с помощью символа, который не входит в алфавит, напр.: P + ‘#’ + S, после чего начать считать префикс-функцию. Как только значение функции будет равно длине образца, то это будет означать, что подстрока найдена:

C = P + '#' + S
PI = create array with C.length
for i = 1 to C.length do
  j = PI[i - 1]
  while j > 0 and C[j] != C[i] do
    j = PI[j - 1]
  end while
  if C[j] == C[i] then
    PI[i] = j + 1
  end if
  if PI[i] == P.length then return TRUE
end for
return FALSE