Question

Question 3. A string p = p₁…p_n is a palindrome if it spells the same string when read backward, that is p_i = p_{n+1 –i} for 1≤ i ≤ n. Design an efficient algorithm for finding all palindromes (of all lengths) in a text. (The pseudo code the algorithm should be provided) (40 points)

Answer 1

Algorithm:

Step 1: Input S (string)

Step 2:  Length = 0 , Flag =0

Step 3: While (S[Length] != NULL)

Length++

Step 4:  I = 0 , J = Length-1

Step 5: While ( I < (Length/2)+1 )

                        If ( S[I] == S[J] )

                                 Flag=0

                        else

                                  Flag=1

                        I++ , J–

Step 6:      If ( Flag == 0 )

                               Print string Is a Palindrome

                     else

                                Print string Is Not a Palindrome

Step 7: End

Pseudo code:

• Input a String
• Initialize Length to zero , Flag to zero
• While String[Length] is not equal to NULL
•    Increment Length
• Initialize I to zero , J to Length-1
• While I is less than (Length/2)+1
•               If String[I] equal to String[J]
•                           Flag=0
•                 else
•                            Flag=1
•                 Increment I , Decrement J
• If Flag equal to zero
•         Print string Is a Palindrome
• else
•         Print string Is Not a Palindrome
• Stop