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