A palindrome is a nonempty string over some alphabet that re

A palindrome is a nonempty string over some alphabet that reads the same forward and backward. Examples of palindromes are all strings of length 1, civic, racecar, abba,… Give a DP algorithm to find the length of the longest palindrome that is a subsequence of a given input string. Write a program to solve this problem.

Examples:

Given the input “character”, your algorithm should return 5 for “carac”.

Given the input “TTATGTGAT”, your algorithm should return 7 for “TATGTAT”. Note that TTATT is a palindromic subsequence but is not the longest.

Solution

#include <stdio.h>

#include <string.h>

//This is a   utility function to print a substring str[low..high]

void printtheSubSequence( char* string, int low, int high )

{

    for( int i = low; i <= high; ++i )

        printf(\"%c\", string[i]);

}

// This is a function that prints the longest palindrome subsequence

of string[].It also returns the length of the longest palindrome

int longestPalSubsequence( char *string )

{

    int n = strlen( string ); // This is to get length of input string

    // The tableone[i][j] will be false if substring string[i..j] is not palindrome else tableone[i][j] will be true

    bool tableone[n][n];

    memset(tableone, 0, sizeof(tableone));

    // The substrings of length 1 are palindromes

    int maxLength = 1;

    for (int i = 0; i < n; ++i)

        tableone[i][i] = true;

    // Now we will check for sub-string of length 2.

    int start = 0;

    for (int i = 0; i < n-1; ++i)

    {

        if (string[i] == string[i+1])

        {

            tableone[i][i+1] = true;

            start = i;

            maxLength = 2;

        }

    }

    //Finally we will check for lengths greater than 2. k is length

    // of substring

    for (int k = 3; k <= n; ++k)

    {

        // This is done to fix the starting index

        for (int i = 0; i < n-k+1 ; ++i)

        {

            // let us get the ending index of substring from starting index i and length k

            int j = i + k - 1;

            // This next step is checking for sub-string from ith index to

            jth index iff string[i+1] to string[j-1] is a

            palindrome

            if (tableone[i+1][j-1] && string[i] == string[j])

            {

                tableone[i][j] = true;

                if (k > maxLength)

                {

                    start = i;

                    maxLength = k;

                }

            }

        }

    }

    printf(\"The Longest palindrome subsquence is is: \");

    printtheSubSequence( string, start, start + maxLength - 1 );

    return maxLength; // This returne length of LPS

}

//This is the driver program to test above functions

int main()

{

  char string[] = \"abcabcdedcacac\";

    printf(\"\ The total Length is: %d\ \", longestPalSubsequence( string ) );

    return 0;

}

Output:

Length is : 5

For cacac