1

Тема: КМП

Хочу сказать большое спасибо автору за этот ресурс. Он самый лучший в своем роде.
У меня есть вопрос.
Читаю статью по алгоритму Кнута-Моррисса_Пратта. Не могу однозначно понять вот эту часть.Количество различных подстрок в строке. Посмотрите  пожалуйста, кто знает  првильно ли я понимаю или нет
Например строка :s=abacaba
Ее  префикс функция. 0 0 1 0 1 2 3
Начнем вычислять количество различных подстрок.
t:=s+'a'. Перевернем ее. t=aabacaba. Ее префикс функция
0 1 0 1 0 1 0 1.  Количество новых подстрок Length(s)+1-pmax=7+1-1=7
Далее
t:=s+'ab'. Перевернем ее. t=baabacaba. Ее префикс функция
0 0 0 1 2 0 0 1 2  Количество новых подстрок Length(s)+1-pmax=7+1-2=6
Далее
t:=s+'aba'. Перевернем ее. t=abaabacaba. Ее префикс функция
0 0 1 1 2 3 0 1 2 3  Количество новых подстрок Length(s)+1-pmax=7+1-3=5
Далее
t:=s+'abaс'. Перевернем ее. t=сabaabacaba. Ее префикс функция
0 0 0 0 0 0 0 1 2 3 4  Количество новых подстрок Length(s)+1-pmax=7+1-4=4

Далее
t:=s+'abaса'. Перевернем ее. t=aсabaabacaba. Ее префикс функция
0 0 1 0 1 1 0 1 2 3 4 5 Количество новых подстрок Length(s)+1-pmax=7+1-5=3

И так далее.

2

Re: КМП

Нет, сначала s='', мы к ней приписываем букву 'a', т.е. считаем префикс-функцию для строки reverse(s+'a'), потом s='a' и мы к ней приписываем букву 'b', т.е. t=reverse('a'+'b'), потом s='ab', и т.д.

UPD Спасибо!