This is a C++ Program that Solves Longest Palindromic Subsequence Problem using Dynamic Programming technique.
You are given a string str. Find the length of longest palindromic subsequence in the given string.
This problem is a variation of the longest common subsequence problem. The required result is simply the LCS of the given string and its reversed string.
Case-1:
str= ADBDCA result = 5 (ADBDA)
Here is source code of the C++ Program to Solve Longest Palindromic Subsequence Problem. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
int longestCommonSubsequece(string str1, string str2)
{
int len1=str1.length(), len2=str2.length();
int i, j;
//create a matrix of order (len1+1)*(len2+1) to tabulate values
int LCS[len1+1][len2+1];
//LCS[i][j]=Length of longest common subsequence of str1[0....(i-1)] and str2[0...(j-1)]
//initializing
for(i=0;i<=len1;i++)
LCS[i][0]=0; //empty str2
for(j=0;j<=len2;j++)
LCS[0][j]=0; //empty str1
//now, start filling the matrix row wise
for(i=1;i<=len1;i++)
{
for(j=1;j<=len2;j++)
{
//if current character of both strings match
if(str1[i-1]==str2[j-1])
{
LCS[i][j]=1+LCS[i-1][j-1];
}
//mismatch
else
{
LCS[i][j]=max(LCS[i-1][j],LCS[i][j-1]);
}
}
}
//now, return the final value
return LCS[len1][len2];
}
int main()
{
string str1;
cout<<"Enter the string - ";
getline(cin,str1);
string str2=str1;
reverse(str2.begin(),str2.end());
cout<<"Longest palindromic subsequence in the input string "<<endl;
cout<<longestCommonSubsequece(str1,str2);
cout<<endl;
return 0;
}
In the main function, we will take input for str1. We will pass this string and its reverse to the function longestCommonSubsequence as parameters. This function will calculate the result using bottom up DP and return the value which is displayed on the standard output.
Case-1: $ g++ longest_palindromic_subsequence.cpp $ ./a.out Enter the string - ADBDCA Longest palindromic subsequence in the input string 5
Sanfoundry Global Education & Learning Series – Dynamic Programming Problems.
To practice all Dynamic Programming Problems, here is complete set of 100+ Problems and Solutions.
- Get Free Certificate of Merit in Data Structure I
- Participate in Data Structure I Certification Contest
- Become a Top Ranker in Data Structure I
- Take Data Structure I Tests
- Chapterwise Practice Tests: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
- Chapterwise Mock Tests: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
- Apply for Computer Science Internship
- Buy Data Structure Books
- Practice Programming MCQs
- Buy Computer Science Books
- Apply for Information Technology Internship