Когда вы соответствующий входной строки, вы можете получить только в состоянии 5 после согласования первые 5 символов шаблона, и первые 5 символов шаблона являются ABABA , Поэтому вне зависимости от того, какую строку ввода вы используете, вы знаете, что текст, предшествующий состоянию 5, является «ABABA».
Так вы, если у вас получится несоответствие в состоянии 5, вы можете создать 4 символа и повторить попытку. Но так как вы знаете, какой текст должен появиться до состояния 5, вам действительно не нужен вводный текст, чтобы выяснить, что произойдет. Вы можете заранее выяснить, в каком состоянии вы попадете, когда вернетесь в одно и то же место.
резервного копирования 4-х символов и перейти в состояние 0:
0: БАБА
А не совпадают, поэтому заранее и перейти в состояние 0
0: ABA
матчи , так что перейти в состояние 1
1: BA
в матчах, перейти в состояние 2
2:
спички, перейти в состояние 3
3:
теперь мы вернулись к тому месту, на входе, где мы видели состояние 5 до, но теперь мы в состоянии 3.
Это всегда произойдет, когда мы получим несоответствие в состоянии 5, поэтому вместо того, чтобы делать это, мы просто сделаем записку, в которой говорится: «Когда мы получим несоответствие в состоянии 5, перейдите в состояние 3».
Обратите внимание, что большинство реализаций КМП фактически составят таблицу сбоев, где failure_table[5]=3. В вашем примере реализовано построение полного DFA[char][state], поэтому он копирует все переходы из состояния 3 в состояние 5 для случаев сбоев. Это говорит о том, что «когда мы получаем несоответствие в состоянии 5, делайте то, что делает состояние 3», и это работает так же.
ПОНЯТЬ ВСЕ ВЫШЕ, прежде чем перейти
Теперь давайте ускорить вычисление этих состояний отказа ...
Когда мы получаем несоответствие в состоянии 5, мы можем использовать DFA мы так чтобы выяснить, что произойдет, если мы создадим резервную копию и возобновим ввод, начиная со следующего возможного совпадения, применив DFA к «BABA». Мы закончили в состоянии 3, так что давайте назовите состояние 3 «состояние отказа» для состояния 5.
Похоже, нам нужно обработать 4 шаблона диаграммы, чтобы рассчитать состояние отказа для состояния 5, но мы уже сделали большинство от этой работы, когда мы рассчитали состояние отказа для состояния 4 - мы применили DFA к «BAB» и закончили в состоянии 2.
Итак, чтобы выяснить состояние отказа для состояния 5, мы просто начинаем с состояние состояния 4 (состояние 2) и обрабатывать следующий символ в шаблоне - «A», который пришел после состояния 4 на входе.
