2086 8М Информатика

На примере ababb
Нам потребуются состояния всех префиксов (пустое, a, ab, aba, abab, ababb (конечное) ), расставим "очевидные" стрелки (из пустого по 'a'  в "a", из "a" по 'b' в "ab" и тд.)
Основная идея - суффикс-ссылки. Суффикс-ссылка должна вести в самый длинный нетривиальный суффикс, то есть
"a"       -> пустое,
"ab"     -> пустое,
"aba"   -> "a",
"abab" -> "ab".
Тогда имеет место следующая конструкция:
"строка-родитель" -буква-> "строка-дочь"
 суффикс-|-ссылка               суффикс-|-ссылка 
"строка-род-суф"   -буква-> "строка-суф-дочь"
Поэтому для пустой строки и первой буквы можем легко сделать переходы, а дальше сделать рекуррентно (то есть через предыдущие) : найти суффикс-ссылку, пройдя по нужной букве суффикс-ссылки родителя, и остальные буквы получить через суффикс ссылку.
Так мы получаем, что из состояния "abab" по букве 'а' нужно попасть в "aba", т.к. туда ведёт суффикс ссылка "ab" по букве 'а'