# The longest common subsequence -- total solution with repeated solution

Solutions:
Finding the longest common subsequence of two strings is a classical dynamic programming problem, which needs two processes roughly:
Suppose the length of two strings is m and n respectively;

• Create a table: c [] [] array records the equal number of characters, traverses m*n times, judges whether the characters are the same, equal max (left, top) + 1, unequal takes max (left, top); at the same time, fill d [] [] array, records the direction of the path, so as to backtrack the longest common subsequence later, 0, 1, 2, 3 respectively represent lefttop, top, left, left==top.

• Backtracking common substring: the more troublesome situation is that there are multiple solutions. You need to define a global variable to store all solutions, and record the common prefixes of the two solutions before branching.

Code:

```#include <iostream>
#include<string>
#include<vector>
#include<set>
using namespace std;

set<string> setOfLCS;

int LCSlen(string str1, string str2, int **d) {
int len1 = str1.size();
int len2 = str2.size();

int **c = new int*[len1 + 1];//Row number
for (int i = 0; i < len1 + 1; i++) {
c[i] = new int[len2 + 1];//Column number
}
for (int i = 0; i < len1 + 1; i++)
c[i][0] = 0;
for (int i = 0; i < len2 + 1; i++)
c[0][i] = 0;
for (int i = 1; i < len1 + 1; i++)
{
for (int j = 1; j < len2 + 1; j++)
{
if (str1[i - 1] == str2[j - 1])//Element i of c corresponds to element i-1 of str1
{
c[i][j] = c[i - 1][j - 1] + 1;
d[i][j] = 0;          //Direction: lefttop
}
else if (c[i - 1][j] > c[i][j - 1])
{
c[i][j] = c[i - 1][j];
d[i][j] = 1;         //Direction: top
}
else if (c[i - 1][j] < c[i][j - 1])
{
c[i][j] = c[i][j - 1];
d[i][j] = 2;       //Direction: left
}
else
{
c[i][j] = c[i][j - 1];
d[i][j] = 3;       //Direction: top==left
}
}
}
return c[len1][len2];
}

void PrintLCS(int **d, string str1, string lcs, int i, int j)
{
while (i >0 && j >0){
if (d[i][j] == 0)
{
string ss;
ss = str1[i - 1];
lcs.insert(0, ss);
i--;
j--;
}
else if (d[i][j] == 1)
i -- ;// top
else if(d[i][j] == 2)
j --; // left
else
{
PrintLCS(d, str1, lcs, i - 1, j);
PrintLCS(d, str1, lcs, i , j - 1);
return;
}
}
setOfLCS.insert(lcs);
}

int main() {
string str1, str2;
cout << "Please enter the first string:" << endl;
cin >> str1;
cout << "Please enter the second string:" << endl;
cin >> str2;
//str1 = "ABCBDAB";
//str2 = "BDCABA";
int len1 = str1.size();
int len2 = str2.size();
int **d = new int*[len1 + 1];//Row number
for (int i = 0; i < len1 + 1; i++) {
d[i] = new int[len2 + 1];//Column number
}
int len = LCSlen(str1, str2, d);
cout << "The length of the longest common subsequence is:" << len << endl;
cout << "The longest common subsequence is:"  << endl;
string lcs;
PrintLCS(d, str1, lcs,len1, len2);
set<string>::iterator beg = setOfLCS.begin();
for (; beg != setOfLCS.end(); ++beg)
cout << *beg << endl;
system("pause");
return 0;
}```

Tags: Programming

Posted on Thu, 02 Apr 2020 20:10:14 -0700 by ballhogjoni