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

Граница Яо может быть достигнута благодаря использованию индексной структуры для обращенного шаблона. Это выполняется при помощи алгоритма обращения сегмента (Reverse Factor), также известного как BDM (Backward Dawg Matching, сопоставление с обращенным ориентированным ациклическим графом слов, ОАГС).

Вместо индексной структуры может использоваться фактор-оракул, поскольку единственной строкой длины m, принимаемая оракулом строки w длины m, является сама строка w. Это выполняется при помощи алгоритма сопоставления с обращенным оракулом (Backward Oracle Matching, BOM) Аллозена, Крочмора и Раффино [1]. На практике его поведение схоже с поведением алгоритма BDM.

Алгоритмы этого типа выполняются за линейное время (это относится к предварительной обработке и поиску) и требуют константного объема памяти в дополнение к объему входных данных.