Последовательное точное сравнение строк: различия между версиями

Первый линейный алгоритм решения задачи ESM появился в 1970-х. Этап предварительной обработки этого алгоритма заключался в вычислении периодов префиксов шаблона или, что эквивалентно, длине самой длинной границы для всех префиксов шаблона. Граница строки является префиксом либо суффиксом строки, отличным от нее самой. Обозначим за next[i] длину самого длинного пути в <math>p_1 ... p_{i - 1}</math>. Рассмотрим попытку сравнения в позиции j, где шаблон <math>p_1 ... p_m</math> выровнен с сегментом <math>t_j ... t_{j + m - 1}</math> текста. Предположим, что первое несовпадение (при сканировании слева направо) имеет место между символами <math>p_i</math> и <math>t_{i + j}</math> для <math>1 \le i \le m</math>. Тогда <math>p_1 ... p_{i - 1} = t_j ... t_{i + j - 1} = u</math> и <math>a = p_i \ne t_{i + j} = b</math>. При сдвиге разумно будет ожидать, что префикс v шаблона будет соответствовать некоторому суффиксу фрагмента u текста. Таким образом, после сдвига сравнение может возобновиться для позиций <math>p_{next[i]}</math> и <math>t_{i + j}</math> без потери каких-либо вхождений P в T и необходимости выполнения возврата в тексте. Существуют два подхода, различающихся в зависимости от того, должен ли <math>p_{next[i]}</math> совпадать с <math>p_i</math>.

Поиск можно осуществить с использованием реализованного алгоритма поиска потомка по умолчанию из детерминированного конечного автомата <math>\mathcal{D}(P)</math>, распознающего язык <math>\Sigma * P</math>. Размер реализации алгоритма составляет O(m) и не зависит от размера алфавита в силу того, что автомат <math>\mathcal{D}(P)</math> имеет m + 1 состояний, m прямых дуг и не более m обратных дуг. Использование конечного автомата для поиска в тексте позволяет получить алгоритм с эффективной задержкой (представляющей собой максимальное время обработки символа текста).