This is a C++ Program that Solves Shortest Common Subsequence Problem using Dynamic Programming technique.
You are given two strings. Find the length of the shortest string that has both the given strings as subsequences.
We can solve this problem by using bottom up DP. We will process the strings character by character and store the results for every pair of prefixes of string 1 and string 2.
string 1 - APQRSTU string 2 - KPLRMNTUO length of shortest string that has both the given strings - 12 (AKPQLRSMNTUO)
Here is source code of the C++ Program to Solve Shortest Common Subsequence Problem. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.
using namespace std;
int shortestCommonSubseq(string str1, string str2)
int len1=str1.length(), len2=str2.length();
cout<<"Enter string 1 ";
cout<<"Enter string 2 ";
cout<<"Length of the shortest common subsequence is "<<endl;
In the main function, we will take input for str1 and str2. We will pass these to the function shortestCommonSubsequence 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++ shortest_common_subsequence.cpp $ ./a.out Enter string 1 PQAMGBMCDKE Enter string 2 ACBACPDE Length of the shortest common subsequence is 14
Sanfoundry Global Education & Learning Series – Dynamic Programming Problems.
To practice all Dynamic Programming Problems, here is complete set of 100+ Problems and Solutions.