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

'''Теорема 1 (Коул и коллеги, 1995 [3]). Минимальное количество сравнений символов для решения задачи ESM в наихудшем случае оказывается больше или равно n + 9/(4m)(n - m) и может быть сделано меньше или равно n + 8/(3(m + 1))(n - m).'''

Первый линейный алгоритм решения задачи 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>.