Хочу сказать большое спасибо автору за этот ресурс. Он самый лучший в своем роде.
У меня есть вопрос.
Читаю статью по алгоритму Кнута-Моррисса_Пратта. Не могу однозначно понять вот эту часть.Количество различных подстрок в строке. Посмотрите пожалуйста, кто знает првильно ли я понимаю или нет
Например строка :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
И так далее.