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

Задача поиска подстроки одна из достаточно распространённых в информатике. Строкой называют последовательность символов (в произвольном порядке) взятых из заданного алфавита. Так например, алфавитом могут быть цифрвы {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. Если символы не совпадают, тогда внутренний цикл прекращает работу. Оговоримся, что если алгоритм отрабатывает все итерации, то переменная цикла будет равна значению правой границы указанного как to N. В таком случае, если длина образца и переменной равны, то это будет означать, что внутренний цикл не нашёл разных символов, а значит подстрока найдена, а индексом начала подстроки является переменная i. В противном случае внешний цикл продолжает работу.

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

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

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

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

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

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

  1. методом деления, когда входное число делится на количество доступных значений хэш-функции, а результатом является остаток от такого деления: hash(k) = k \mod r;
  2. метод середины квадрата умножает входное число само на себя, а из его середины берутся необходимое количество знаков;
  3. метод умножения имеет вид 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)

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

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

Наивный алгоритм подсчёта префикс-функции для произвольной строки S при всех значениях {\displaystyle 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[k] == C[i] then
    PI[i] = j + 1
  end if
  if PI[i] == P.length then return TRUE
end for
return FALSE

Сообщить об опечатке

Текст, который будет отправлен нашим редакторам: