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.
User avatar
ymondelo20
COJ Administrator
Posts: 1968
Joined: Sun Nov 13, 2011 12:32 pm
Location: Universidad de las Ciencias Informáticas
Gender: None specified
Contact:

3672 - Palindrome

Postby ymondelo20 » Mon Jun 13, 2016 10:42 pm



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

User avatar
isaac
Posts: 83
Joined: Mon Oct 26, 2015 6:20 pm
Gender: None specified

Re: 3672 - Palindrome

Postby isaac » Fri Jun 17, 2016 7:56 am

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)


Return to “Problem set”

Who is online

Users browsing this forum: No registered users and 1 guest