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

После первого решения Галила и Сейфераса другие варианты были предложены Крочмором и Перреном [6] и Риттером [6]. Алгоритмы разбивают шаблон на две части; вначале они выполняют поиск правой части шаблона слева направо, а затем, если не обнаружено несовпадений, ищут левую часть. Разбиение может представлять собой идеальную факторизацию [8] или критическую факторизацию [6] либо основываться на лексикографически максимальном суффиксе шаблона [13]. Еще одно решение Крочмора [2] представляет собой вариант KMP [11]: оно на лету вычисляет нижние границы периодов префиксов шаблона и не требует предварительной обработки.