When learning shell script, a very common script which is given as a task in schools is to write a script to check if a string is a palindrome or not. I am presenting two solutions of this simple problem. A palindrome is a string whose reverse is same as the string itself. Like “madam” is a palindrome but “hello” is not

Script 1

The first one uses the well known method, which scans from the 1st to the (n/2)th character and matches ith and (n-i)th characters for a match. One mismatch in the scanning leads to immediate termination of the scanning as it is not a palindrome.
To match the ith and the (n-i)th character we will use bash built-in feature to extract characters.

#!/bin/bash
# Shell script to test if a string is a palindrome
# This uses the well known method to scan half the string matching
# the i and len - i chars, if one mismatch is found it quits immediately

echo "Enter a String : "
read string

i=0
len=${#string}

#get the mid value upto which the comparison would be done
mid=$(($len/2))

while [ $i -lt $mid ]
  do
    if [ "${string:$i:1}" != "${string: -$(($i+1)):1}" ]
      then
      echo "\"$string\" IS NOT a Palindrome"
      exit
    fi
    i=$(($i+1))
done
echo "\"$string\" IS a Palindrome"

${string: 0: 1} will cut one character from the 0th character of the string, ie it will only get the 0th character. ${string: 2: 1} will get the third character. Also ${string: -1: 1} will cut the last one character, ${string: -3: 1} will get the third last character. i is initialized to zero. So with this construct we need to match ${string: $i: 1} and ${string: -$(($i+1)): 1}
The character indices i starts from 0, runs less than len/2. Let the value of len be 5 for a case. It first matches position (0,-1) and position (1,-2). If both of the characters in the position matches then it is a palindrome.

Here’s a short dry run

+-+-+-+-+-+
|1|2|3|4|5|
+-+-+-+-+-+
|m|a|d|a|m|
+-+-+-+-+-+

i=0
len=5
loop runs until i less than  5/2 = 2

Matches: ${string: $i: -$(($i+1))}
Iteration 1: location i=0 = "m" AND location (-1) = "m"
Iteration 2: location i=1 = "a" AND location (-2) = "a"
IS Palindrome

If the string was "mOdam" then the scanning would stop in Iteration 2 , and immediately exit

Read more about the bash substring feature here: http://mywiki.wooledge.org/BashFAQ/073

Script 2

In this script we will use cut command with the -c option to extract the characters with the position number. Positions and fields of cut start from 1

The script is below

#!/bin/bash
# Shell script to test if a string is a palindrome
# This uses the well known method to scan half the string matching
# the i and len - i chars, if one mismatch is found it quits immediately

echo "Enter a String : "
read string

i=1

#calculate the length of 'string'+1 the 1 is added because the string index
#starts at 1. If length is 5+1=6 then first 1 and 6-1=5 will be matched, and so on
len=$((${#string}+1))

#get the mid value upto which the comparison would be done
mid=$(($len/2))

while [ $i -le $mid ]
  do
    if [ "$(echo "$string" | cut -c$i)" != "$(echo "$string" | cut -c$(($len-$i)))" ]
      then
      echo "\"$string\" IS NOT a Palindrome"
      exit
    fi
    i=$(($i+1))
done
echo "\"$string\" IS a Palindrome"

Note that because the ${#string} calculates the length ‘n’ and the index starts at 1 so the comparison would be done between 1 and n-1 , 2 and n-2 and so on, but we need to compare 1 with n , 2 with n-1 and so on . That’s why we add 1 to the length of the string so now the length of the string is n+1 so we can now compare 1 and (n+1)-1=n and so on.

Here’s a short dry run

+-+-+-+-+-+
|1|2|3|4|5|
+-+-+-+-+-+
|m|a|d|a|m|
+-+-+-+-+-+

i=1
len=6 (including the terminating NULL, and indexes start from 1)
loop runs until 6/2 = 3

Matches:
Iteration 1: location 1 = "m" AND location (6-1) = "m"
Iteration 2: location 2 = "a" AND location (6-2) = "a"
Iteration 3: location 3 = "d" AND location (6-3) = "d"
IS Palindrome

If the string was "mOdam" then the scanning would stop in Iteration 2 , and immediately exit

Script 3

There is another shortcut method. But this needs the rev command. This is a part of util-linux-ng package which should be installed in all GNU+Linux systems. The rev command reverses lines of a file. We echo the entered string and pipe it to rev to get the reverse and match if the reversed string and the original string was the same.

#!/bin/bash

# Shell script to test if a string is a palindrome
# This simply uses the 'rev' command found in util-linux-ng package
# and checks if the reverse of the string is same as the original

echo "Enter a String : "
read string

if [ "$(echo $string | rev)" = "$string" ]
  then
    echo "\"$string\" IS a Palindrome"
  else
    echo "\"$string\" IS NOT a Palindrome"
fi

Update

25.02.2010 : String length calculation changed from echo “$string” | wc -c to ${#string}
14.03.2010 : New script added to cut characters with bash inbuilt feature

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s