Property of Palindromic Tree , ACM Timus 2058

Правка en1, от V_2, 2017-06-12 13:22:24

I am currently solving ACM Timus 2058 , a problem about palindromes.

In palindromic tree 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.

 [  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" ] 

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 )"

Eg:

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

And then Y would be a palindrome too.

Property of Palindromic Tree ( depends on property-1)

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.

So I want to ask : " Is property-1 correct?" If not then can anyone provide me any example? I think everyone face this property when solving ACM Timus 2058 (I may be wrong though).

Thanks in advance.

[ 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 ]
Теги #help, palindromic tree, ural, 2058, #palindrome, 2044, 2057

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en4 Английский V_2 2017-06-14 08:33:31 1315 Extension of the proof , Last Update , Completed
en3 Английский V_2 2017-06-12 18:03:23 272 Proof of Correctness of the property has been
en2 Английский V_2 2017-06-12 17:29:28 230 Definition of X has been changed . Extra example showing the property has been added.
en1 Английский V_2 2017-06-12 13:22:24 2405 Initial revision (published)