Previous: 11.3 More Example Programs
Up: 11.3 More Example Programs
Next: 11.3.2 Words
Previous Page: 11.3 More Example Programs
Next Page: 11.3.2 Words

11.3.1 Palindromes

Our next task is:

PALI: Read strings and check if each is a palindrome.

A palindrome is a string that reads the same forwards and backwards, for example:

able was i ere i saw elba

The algorithm is simple: compare the reverse of the string with the original string. If they are the same, the string is a palindrome.

while not EOF, read a string s
         copy reverse of s into t

         if s and t are equal,
              s is a palindrome
         else
              s is not a palindrome

The driver follows the algorithm closely, as seen in Figure 11.11. We will use a function, revcpy(), to copy the reverse of the string.

We must write the function revcpy() to copy one string into another in reverse order. To see how the algorithm for this function should proceed, we will work with the indices in the source and destination strings as shown below:

The string, src, is shown with the terminating NULL and the source index, sind, must start at the last character of src and decrease as each character is copied. In the destination string, dest, the index, dind, must start at 0 and increase as each character is copied. When the source index becomes negative, all characters have been copied in reverse order from the source. After all the characters are copied, a terminating NULL must be added to the destination string. Here is the algorithm:

initialize sind to the last index of src and dind to 0
    while sind is >= 0
         copy from src to dest
         increment dind and decrement sind
    add a NULL to dest

Here is a sample session:

• ***Palindrome Test***
• Type strings, EOF to quit
• this is it
• this is it: not a palindrome
• able was i ere i saw elba
• able was i ere i saw elba: a palindrome
• '136D