#DOTD: Palindromes

11 Jun 2017

An exact palindrome is a word that is equivalent to its reverse. For example: X = abbacabba is exactly the same as XRabbacabba. You can also imagine that there is a mirror in the centre of X (on top of the character c.


An approximate palindrome allows for up to k errors. You can think of this as allowing for k edit distance operations to transform one half of the string into the reverse of the other). For example, Y = abbacacba is and approximate palindrome because abba  =k abca, where = 1. Note that we ignore the here, as it is in the very centre.


An even palindrome is one that has an even number as its length, for example, Z = abcbbcba of length 6.


Can you guess the definition of an odd palindrome? String X = abbacabba is an example.


The radius of a palindrome is half of its length. If it's an odd palindrome, you have to remove the odd character in the centre before computing its radius. The radii of all of the example strings mentioned above are 4.



Share on Facebook
Share on Twitter
Share on LinkedIn
Please reload

Please reload

Related Posts
PhDomics by Fatima