48
правок
Изменения
м
Нет описания правки
* <tex> s = 0 </tex>
* <tex> T = \left\{m\right\} </tex>
* <tex> \delta(q, a) = \sigmasigma_p(p[1 \dots q] + a) </tex>, где <tex>q</tex> {{---}} это состояние, <tex>a</tex> {{---}} символ, по которому осуществляется переход, a "<tex>+</tex>" {{---}} операция конкатенации (<tex>p[1, 0] = \varepsilon </tex>).
Таким образом, если часть текста, в котором мы ищем образец, уже пропущена через [[Детерминированные_конечные_автоматы|автомат]], то текущее состояние отражает, сколько последних символов этой прочитанной части совпадает с началом нашего образца. Если мы пришли в допускающее состояние, значит последние <tex>m</tex> символов полностью совпадают с образцом и мы нашли включение.
'''for''' a <tex>\in \Sigma</tex>
'''if''' q > 0 '''and''' a <tex>\ne</tex> p[q + 1]
<tex>\delta</tex>(q, a) = <tex>\delta</tex>(<tex>\pipi_p</tex>(q), a)
'''if''' c = p[q + 1]
<tex>\delta</tex>(q, a) = q + 1
