3672 - Palindrome

Discussion around the problems of the COJ.
Forum rules
Remember that posting AC code is not allowed here. If you are going to ask a question or to post a solution, describe your algorithm instead. Posting AC code will be penalized.
Post Reply
User avatar
ymondelo20
Posts: 1968
Joined: 7 years ago
Location: Universidad de las Ciencias Informáticas
Gender: None specified
Contact:

3672 - Palindrome

Post by ymondelo20 » 2 years ago



"Every problem has a simple, fast and wrong solution" OJ's Main Law. ;)

User avatar
isaac
Posts: 83
Joined: 3 years ago
Gender: None specified

Re: 3672 - Palindrome

Post by isaac » 2 years ago

Si se quiere obtener el mayor palindrome que es subsecuencia de una cadena dada, bastaria con realizar un LCS entre la cadena y ella misma, pero invertida. Como esto nos da la longitud del mayor palindrome que existe en la cadena, bastaria con restarle al total de caracteres de la cadena, la longitud del LCS antes mencionado, lo que representa la cantidad de caracteres que no pertenecen al palindrome y deben ser agregados para emparejar la situacion y formar un palindrome. En resumen, seria N - LCS(cadena, cadena_invertida)

Post Reply

Return to “Problem set”