Алгоритм поиска подстроки, основанный на конечных автоматах

С этого момента мы будем говорить о строках в понимании языка С.

Итак, в строке S, strlen(S)==N, следует найти все вхождения подстроки W, strlen(W)==M, т.е. следует найти все такие 0£ i £N-M, что strncmp(S+i,W,M)==0.

Будем говорить, что строка b является префиксом строки a, если

strlen(b)<=strlen(a) && strncmp(b,a,strlen(b))==0.

Будем говорить, что строка b является суффиксом строки a, если

strlen(b)<=strlen(a) && strcmp(b,a+strlen(a)-strlen(b))==0.

Основная идея алгоритма следующая: будем последовательно добавлять к входной строке S по одному символу из входного потока данных. При этом, каждый раз будем вычислять значение функции h(S,W), равной максимальной длине l суффикса строки S, совпадающего с префиксом строки W длины l:

strncmp(S+strlen(S)-l,W,l)==0

Например, для S=(ababa), W=(abac): h(S,W)= 3.

Если, при этом, выполнится условие

h(S,W)==strlen(W)

то это будет обозначать, что найдено вхождение W в строку S.

Допустим, что в некоторый момент мы знаем значение функции h(S,W). Пусть строка S2 получена с помощью добавления очередного символа a из входного потока данных в конец строки S.

Легко увидеть, что h(S2,W) <= h(S,W)+1 (иначе, мы сразу получим, что строка S имеет суффикс длины большей h(S,W), совпадающий с префиксом W), но зная значение h(S,W) мы сразу получаем значения h(S,W) последних символов S (это – первые h(S,W) символов строки W). Т.о. значение функции h(S2,W) может быть вычислено исходя из знания значения h(S,W) и a.

Итак, мы строим конечный автомат, в котором состояние системы задается величиной H= h(S,W). В качестве входного алфавита будут выступать символы, текста. Принимающим будет такое состояние H, когда H==strlen(W).Начальное состояние H₀=0. О вычислении функции перехода поговорим позднее.

Итак, легко увидеть, что, если не задумываться о вычислении функции перехода, то основная часть алгоритма поиска выполняется за время T=Q(N), где N – длина входной последовательности текста.

Функцию перехода предлагается вычислять в лоб. Т.е. для случая, когда ищется строка W и когда алфавит состоит из 256 символов, строится таблица tab из 256 столбцов и strlen(W) строк. j- ый столбец будет соответствовать появлению символа с кодом j, а i- ая строка будет соответствовать состоянию автомата i. Для получения значения tab[i][j] следует рассмотреть строку, состоящую из i первых символов строка W с добавленным в конец символом с кодом j. Длина максимального суффикса полученной строки, совпадающего с префиксом W, будет искомым значением tab[i][j].

Для получения значения tab[i][j] нужно не более i раз сравнить подстроку W с подстрокой полученной строки. Итого, tab[i][j] вычисляется за время O(M²). Все значения tab[i][j] вычисляются за время O(256M³), где 256 – количество символов входного алфавита, M – длина искомого слова. Легко увидеть, что для данного алгоритма данная оценка точна. Т.о. мы доказали следующую теорему

Теорема. Поиск подстроки длины M, состоящей из символов алфавита из K символов, в тексте длины N с помощью предложенного алгоритма, использующего конечные автоматы, требует основного времени T₁=Q(N). На подготовку, зависящую только от искомой подстроки и размера входного алфавита, требуется время T₀=Q(K M³).

Лекция 15

Дата добавления: 2015-10-30