Строка <tex>xAx</tex> {{---}} это единственная подстрока-палиндром строки <tex>p+x</tex>, которой, возможно, нет в <tex>p</tex> (все другие подстроки-палиндромы есть). Чтобы понять почему это так, нужно обратить внимание на то, что все новые подстроки-палиндромы, которых не было в <tex>p</tex>, должны оканчиваться на символ <tex>x</tex>, и поэтому должны быть палиндромом-суффиксом строки <tex>p+x</tex>. Из-за того, что <tex>xAx</tex> {{---}} наибольший палиндром-суффикс строки <tex>p+x</tex>, все остальные меньшие палиндромы-суффиксы этой строки уже есть в каком-то префиксе строки <tex>xAx</tex> (т.к. для каждого суффикса палиндрома есть равный ему префикс) и, соответственно, уже есть в <tex>p</tex>.
SoТаким образом, to process new letter чтобы обработать очередной символ <tex>x we just go along suffix links of </tex>, нужно просто спуститься по суффиксным ссылкам строки <tex>t until we find an appropriate </tex> до тех пор, пока мы не найдем подходящую строку <tex>A </tex> (and we always find someпричем мы всегда можем найти такую строку, possibly of length возможно длины -1 if we trace suffix links back to the roots, если очередная суффиксная ссылка будет вести в корень). Then we check if there is an edge on letter Затем нужно проверить, есть ли уже ребро по символу <tex>x from the node corresponding to </tex> из вершины, соответствующей <tex>A</tex>, and if notи если нет, set this edge going to the new node corresponding to добавить это ребро в новую вершину <tex>xAx</tex>.
What about suffix link of the node Теперь нужно добавить суффиксную ссылку из вершины <tex>xAx? If this node already existed before</tex>. Если эта вершина уже существовала до добавления символа <tex>x</tex>, the suffix link was also already set and we don't need to do anythingничего делать не нужно {{---}} суффиксная ссылка итак указывает на правильную вершину. If not, then we need to find the largest suffixИначе на нужно найти наибольший палиндром-palindrome of суффикс строки <tex>xAx</tex>, which will be in a form of который будет иметь вид <tex>xBx</tex>, where где <tex>B is some string</tex> {{---}} это некоторая строка, возможно, possibly emptyпустая. By the same logic that we used beforeСледуя той же логике, которую мы использовали раньше, <tex>B is a suffix</tex> {{---}} это палиндром-palindrome of суффикс строки <tex>p and can be reached from </tex> и может быть достигнут из <tex>t by suffix links</tex> по суффиксным ссылкам.
== Реализация ==
