# #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 XR =Â abbacabba. 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Â kÂ = 1. Note that we ignore theÂ cÂ 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.

Â

[161]