Изменения

Строка <tex>xAx</tex> {{---}} это единственная подстрока-палиндром строки <tex>p+xpx</tex>, которой, возможно, нет в <tex>p</tex> (т.е. все другие подстроки-палиндромы есть).

Заметим, что все новые подстроки-палиндромы, которых не было в <tex>p</tex>, должны оканчиваться на символ <tex>x</tex>, и поэтому должны быть палиндромом-суффиксом строки <tex>p+xpx</tex>. Из-за того, что <tex>xAx</tex> {{---}} наибольший палиндром-суффикс строки <tex>p+xpx</tex>, все остальные меньшие палиндромы-суффиксы этой строки уже есть в каком-то префиксе строки <tex>xAx</tex> (т.к. для каждого суффикса палиндрома есть равный ему префикс) и, соответственно, уже есть в <tex>p</tex>.}}