Начал изучать алгоритм Ахо-Корасик и у меня появился вопрос по нему.
Пусть словарь состоит из одного слова:
aab
А строка в которой ищем такая:
aaab
Сначала он будет переходить по рёбрам а, а потом ребра а уже не будет и он должен перейти по суффиксной ссылке. Она ведёт в корень, ведь так? И в итоге вхождение подстроки не будет найдено. Объясните, пожалуйста, где я ошибся.
Пусть словарь состоит из одного слова:
aab
А строка в которой ищем такая:
aaab
Сначала он будет переходить по рёбрам а, а потом ребра а уже не будет и он должен перейти по суффиксной ссылке. Она ведёт в корень, ведь так? И в итоге вхождение подстроки не будет найдено. Объясните, пожалуйста, где я ошибся.
нет, не в корень, так как для второй вершины в боре суффиксным переходом будет вершина 1. Бор: Root — a — a — b 0 — 1 — 2 — 3 То есть для вершины 2 (строка aa) суффиксом максимальной длины встречающаяся в боре будет строка "а", которой соответствует первая вершина.
Из второй вершины алгоритм попытается пройти по букве а. У него не получится, и он пойдет по суффиксной ссылке в первую вершину, а затем попытается уже ИЗ НЕЕ пойти во вторую, что он с успехом и сделает, вернувшись во вторую вершину. Итого по букве b он пойдет из второй вершины в третью, и вхождение будет найдено!
Извините, немного не попал...
Для одной строки ахо-корасик работает как префикс функция (алгоритм Кнута-Морриса-Пратта). Это какбы обобщение префикс функции на бор.