Palindrome

From Algorithmist
Jump to navigation Jump to search

A palindrome is a string that reads the same forwards as backwards. For example, "555", "12344321", "racecar" and "ABLE WAS I ERE I SAW ELBA" are palindromes.

Palindromes frequently occur in programming problems; so it is useful to know some of their properties.

It is often convenient to think of two kinds of palindromes separately:

  1. Even-length palindromes: These have a "first half" whose reverse is the second half. In "12344321", the second half "4321" is simply the reverse of the first half "1234".
  2. Odd-length palindromes: These have a first half, a central character, and then the reverse of the first half. For instance, "racecar" can be thought of as "rac", followed by "e", followed by "car", the reverse of "rac".

In general, we can think of a palindrome of length as being specified entirely by its first characters: if the palindrome is of length and its first characters form the string , then = + , where denotes concatenation and is the reverse of the string formed by the first characters of (or equivalently, ). Among other things, this means that to compare two palindromes of the same length, it is enough to compare their corresponding s.

Also, it is important to watch out whether the problem asks for palindromic strings (strings over some given alphabet), or palindromic numbers. Working with palindromic numbers of a given length is usually not exactly the same as working with palindromic strings over the alphabet , because of the restriction that the leading digit cannot be . Although this is a minor difference, ignoring it can be costly.

The observations above make it easy to do several operations on palindromes:

  • Generating all palindromes of a given length , in lexicographic order. This involves simply looping over all strings of length . This is especially easy when the palindromes are numbers:
for tnum =  to 
 do
    t = tnum as a string
    t'= prefix of t of length 
    u = reverse(t')
    print t+u
 done
  • Finding the next greater (lexicographically) palindrome, given a string. Let the string be of length , and and be defined as before. Get the string as before. If this string (which will be a palindrome) is greater than the given string, then we are done. Else, we increment by (as a number) and form the new palindrome; this is guaranteed to be greater than the given string. Note that if (and only if) the given string consisted only of s, this algorithm will increase the length of the string, but it still happens to work, without any need for special-casing.