I am currently solving [ACM Timus 2058](http://acm.timus.ru/problem.aspx?space=1&num=2058) , a problem about palindromes. ↵
↵
In [palindromic tree](http://adilet.org/blog/25-09-14/) every node represents a distinct palindrome (lets say , p) in a string and this node links to another node which represents the longest proper suffix of it(p) which is a palindrome. Eg. If a node u represents "aabaa" then it's link will be a node v which represents "aa", since "aa" is **longest palindromic suffix** of "aabaa".↵
↵
When solving that problem, I observed an interesting property (and I could not prove it's correctness) about palindrome.↵
<br/>↵
<pre>↵
[↵
Note : If X is a string , then here by (X^n) I mean concatenation of n **X** string. ↵
If X="ab" then X^3= "ababab".↵
And XY represent concatenation of X and Y . X="a" ,Y="b" then XY="ab"↵
]↵
</pre>↵
↵
**Property-1:** " _If a palindrome **P** has longest palindromic suffix **Q** and `if | length of Q | >= (| length of P | / 2)` then palindrome **P** has a structure like `(X^n)Y` where n>=2 , X and Y are string ( | Y | < | X | and Y could be a null string ). `Here, X will be a prefix of P and length of X= |P|-|Q|.`
<br/>↵
↵
Eg-1 : ↵
If X='aba' and Y=''(NULL) then 'abaaba' = (X^2), 'abaabaaba' = (X^3), 'abaabaabaaba = (X^4)' etc↵
If X='bba' and Y='bb' then 'bbabbabb' = [(X^2)Y], 'bbabbabbabb' = [(X^3)Y] , 'bbabbabbabbabb' = [(X^4)Y] etc↵
↵
EG (of property): P="bbabbabbabb" and longest suffix palindrome of it is Q="bbabbabb" then by property X="bba".↵
Now P can be represent as XXXY, where Y="bb" .↵
↵
And then Y would be a palindrome too.↵
↵
<spoiler summary="Property of Palindromic Tree ( depends on property-1)">↵
If Property-1 is correct then we can claim that " _From a node u in palindromic tree if we climb up the tree with its link then it will take maximum `O(logn)` time to reach a node which node represents a palindrome with the similar structure `(X^n)Y`_ "↵
</spoiler>↵
↵
But everything depends on **Property-1**. I did some paper works and found it happens. But I think it is not enough to find the correctness of the property.↵
↵
**Edit:** This property is correct, as symbols on positions that differs by |P| - |Q| are equal. Thanks [user:Um_nik,2017-06-12] for providing the proof. " _From a node u in palindromic tree if we climb up the tree with its link then it will take maximum `O(logn)` time to reach a node which node represents a palindrome with the similar structure `(X^n)Y`_ "↵
</spoiler>↵
↵
But everything depends on **Property-1**. I did some paper works and found it happens. But I think it is not enough to find the correctness of the property.↵
↵
**Edit:** This property is correct, as symbols on positions that differs by |P| - |Q| are equal ( Thanks [user:Um_nik,2017-06-12] for providing the proof).↵
↵
Why symbols on positions that differs by |P|-|Q| would be equal? You can find the proof [here](https://docs.google.com/document/d/1LKDnv8BUwvFUPsK_5rmBoW2vBtLY3yPGdMp0Sgrp2zM/edit?usp=sharing)↵
↵
↵
<pre>[ Sorry For my bad English. I tried my best to explain ,though I am not good at explaining. If you don't understand any part of it , you can ask me ]</pre>↵
↵
In [palindromic tree](http://adilet.org/blog/25-09-14/) every node represents a distinct palindrome (lets say , p) in a string and this node links to another node which represents the longest proper suffix of it(p) which is a palindrome. Eg. If a node u represents "aabaa" then it's link will be a node v which represents "aa", since "aa" is **longest palindromic suffix** of "aabaa".↵
↵
When solving that problem, I observed an interesting property (and I could not prove it's correctness) about palindrome.↵
<br/>↵
<pre>↵
[↵
Note : If X is a string , then here by (X^n) I mean concatenation of n **X** string. ↵
If X="ab" then X^3= "ababab".↵
And XY represent concatenation of X and Y . X="a" ,Y="b" then XY="ab"↵
]↵
</pre>↵
↵
**Property-1:** " _If a palindrome **P** has longest palindromic suffix **Q** and `if | length of Q | >= (| length of P | / 2)` then palindrome **P** has a structure like `(X^n)Y` where n>=2 , X and Y are string ( | Y | < | X | and Y could be a null string ). `Here, X will be a prefix of P and length of X= |P|-|Q|.`
<br/>↵
↵
Eg-1 : ↵
If X='aba' and Y=''(NULL) then 'abaaba' = (X^2), 'abaabaaba' = (X^3), 'abaabaabaaba = (X^4)' etc↵
If X='bba' and Y='bb' then 'bbabbabb' = [(X^2)Y], 'bbabbabbabb' = [(X^3)Y] , 'bbabbabbabbabb' = [(X^4)Y] etc↵
↵
EG (of property): P="bbabbabbabb" and longest suffix palindrome of it is Q="bbabbabb" then by property X="bba".↵
Now P can be represent as XXXY, where Y="bb" .↵
↵
And then Y would be a palindrome too.↵
↵
<spoiler summary="Property of Palindromic Tree ( depends on property-1)">↵
</spoiler>↵
↵
But everything depends on **Property-1**. I did some paper works and found it happens. But I think it is not enough to find the correctness of the property.↵
↵
**Edit:** This property is correct, as symbols on positions that differs by |P| - |Q| are equal. Thanks [user:Um_nik,2017-06-12] for providing the proof.
</spoiler>↵
↵
But everything depends on **Property-1**. I did some paper works and found it happens. But I think it is not enough to find the correctness of the property.↵
↵
**Edit:** This property is correct, as symbols on positions that differs by |P| - |Q| are equal ( Thanks [user:Um_nik,2017-06-12] for providing the proof).↵
↵
Why symbols on positions that differs by |P|-|Q| would be equal? You can find the proof [here](https://docs.google.com/document/d/1LKDnv8BUwvFUPsK_5rmBoW2vBtLY3yPGdMp0Sgrp2zM/edit?usp=sharing)↵
↵
↵
<pre>[ Sorry For my bad English. I tried my best to explain ,though I am not good at explaining. If you don't understand any part of it , you can ask me ]</pre>↵
