Longest Common Subsequence (LCS)

"ABCD" and "BCE" : LCS = BC length of 2

Example s1 = "ABCD" and s2 = "BC" where l1 = 4(s1.length) and l2 = 2(s2.length)

find out the LCS of this two string

---

Steps:

• make a 2D table of [l1+1][l2+1] or [l2+1][l1+1] format

• fill row[0] and col[0] with zeros

  	col[0]	A	B	C	D
  row[0]	0	0	0	0	0
  B	0
  C	0

• compare each row's character with every column's character

  • if matched then place there : previous diagonal box value + 1

  • else place there : max(left box value, top box value)

    for(int i=1; i<=len1; i++)
    {
        // iterate second string
        for(int j=1; j<=len2; j++)
        {
            /*
                whether current index of string1 and string2 item match each
                other then set table value for this two index
                previous diagonal index + 1;
                otherwise set the maximum of corresponding row neighbor item
                and corresponding column item.
            */
            if(str1.at(i-1) == str2.at(j-1))
                table[i][j] = table[i-1][j-1]+1;
            else
                table[i][j] = max(table[i-1][j],table[i][j-1]);
        }
    }

---

How the table is building

	col[0]	A	B	C	D
row[0]	0	0	0	0	0
B	0	0	1	1	1
C	0	1	1	2	2

answer : 2 (LCS length)

Use backtrack for iterating the LCS string

    for(int i=len1,j=len2,index=table[len1][len2]; i!=0 && j!=0; )
    {
        if(str1.at(i-1) == str2.at(j-1))
        {
            // set the char in corresponding index
            seq.at(index-1) = str1.at(i-1);
            i--;
            j--;
            index--;

        }
        // check current value comes from which neighbor
        else if(table[i][j-1] < table[i-1][j])
            i--;
        else
            j--;
    }

---

Program Code