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

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

'''Теорема 6 (Крочмор и др., 1994 [4]). Поиск может быть выполнен за оптимальное ожидаемое время O((log m/m) x n) с использованием суффиксного конечного автомата или суффиксного дерева реверсивного шаблона.'''