4551
правка
Последовательное точное сравнение строк: различия между версиями
Материал из WEGA
Последовательное точное сравнение строк (посмотреть исходный код)
Версия от 16:03, 25 апреля 2019
, 25 апреля 2019→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 46: | Строка 46: | ||
Алгоритм сканирует символы в окне справа налево, начиная с самого правого символа. В случае несовпадения (либо полного совпадения с шаблоном) он использует две предварительно вычисляемые функции для сдвига шаблона вправо. Эти две функции сдвига носят название сдвига плохого символа и сдвига хорошего суффикса. Они основаны на следующих наблюдениях. Предположим, что несовпадение обнаруживается между символом | Алгоритм сканирует символы в окне справа налево, начиная с самого правого символа. В случае несовпадения (либо полного совпадения с шаблоном) он использует две предварительно вычисляемые функции для сдвига шаблона вправо. Эти две функции сдвига носят название ''сдвига плохого символа'' и ''сдвига хорошего суффикса''. Они основаны на следующих наблюдениях. Предположим, что несовпадение обнаруживается между символом <math>p_i = a</math> шаблона и символом <math>t_{i + j} = b</math> текста после попытки в позиции j. Тогда <math>p_{i + 1} ... p_m = t_{i + j + 1} ... t_{j + m} = u</math> и <math>p_i \ne t_{i + j}</math>. Сдвиг хорошего суффикса заключается в выравнивании сегмента <math>t_{i + j + 1} ... t_{j + m}</math> с его самым правым вхождением в P, предшествующим символу, отличному от <math>p_i</math>. Еще один вариант, называемый ''сдвигом лучшего суффикса'', заключается в выравнивании сегмента <math>t_{i + j} ... t_{j + m}</math> с его самым правым вхождением в P. Вычисление обоих вариантов требует O(m) времени и памяти, независимо от размера алфавита. Если такого сегмента не существует, сдвиг заключается в выравнивании самого длинного суффикса v строки ti+j+1 … tj+m с совпадающим префиксом x. Сдвиг плохого символа заключается в выравнивании символа текста ti+j с его самым правым вхождением в p1 … pm-\-. Если ti+j не встречается в шаблоне и никакое вхождение P в T не перекрывает символ ti+j, тогда левый конец шаблона выравнивается с символом в позиции i + j + 1. В этом случае поиск может быть выполнен за время O(n/m) в наилучшем случае. | ||
