Сопоставление с конечными автоматами

Недавно я читал знаменитую книгу по разработке алгоритмов CLRS (Cormen, Leiserson, Rivest, Stain, 3-е издание). Между классическим алгоритмом KMP и алгоритмом Рабина-Карпа есть часть, касающаяся сопоставления строк с конечными автоматами. Таким образом, алгоритм создает автоматы в соответствии с шаблоном и начинает обработку строки. введите описание изображения здесь

Поэтому здесь, в этом примере, алгоритм ищет шаблон «ababaca» во входной строке. Так что все кажется логичным, кроме двух вещей.

Почему нет пути к предыдущим состояниям из состояния 4, когда я добираюсь до «b», потому что в этом случае у меня будет «ababb», что уже является несоответствием ???? И что происходит, когда я читаю «b» или «c» из состояния 6 ?? Есть что-то, что я неправильно понял? Также нет чтения «c» падежа из состояний от 0 до 4 и так далее ..

1

Решение

Проверьте стол (б).
Все состояния, о которых вы говорите, помечены как 0. Итак, вы возвращаетесь к началу.
На изображении вы получите множество ребер обратно в 0, чтобы они не отображались (для ясности).

3

Другие решения


По вопросам рекламы [email protected]