LCS，

LCS，

1. Longest Common Substring
The Longest Common Substring (LCS) problem is as follows:
Given two strings s and t, find the length of the longest string r, which is a substring of both s and t.
Substring is contiguous series of characters

Analysis:
typical Dynamic programming problem. We need find the state transition relation.

Both time and space complexity of O(m*n).

Let’s say the sub-problem (state) P[i][j] to be the length of the longest substring ends at i of s and j of t. Then the state equations are

P[i][j] = 0 if s[i] != t[j];
P[i][j] = P[i - 1][j - 1] + 1 if s[i] == t[j].

string longestCommonSubstring(string s, string t) 
{
    int m = s.size(), n = t.size();
    vector<vector<int> > dp (m, vector<int>(n, 0));
    int start = 0, len = 0;
    for (int i = 0; i < m; ++i)
        for (int j = 0; j < n; ++j)
        {
            if (i == 0 || j == 0) dp[i][j] = (s[i] == t[j]);
            else if (s[i] == s[j])
                dp[i][j] = dp[i - 1][j - 1] + 1;
            else dp[i][j] = 0;
            //else dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);
            if (dp[i][j] > len){
                len = dp[i][j];
                start = i - len + 1;
            } 
        }
        return s.substr(start, len);
}

---

2. Longest Common Sequence
Subsequence is not necessarily contiguous.

Analysis:
Let’s say the sub-problem (state) P[i][j] to be the length of the longest substring ends at i of s and j of t. Then the state equations are

P[i][j] = max(p[i - 1][j], p[i][j - 1]) if s[i] != t[j];
P[i][j] = P[i - 1][j - 1] + 1 if s[i] == t[j].

Costs O(m*n) time complexity and O(m*n) space complexity

Code:

int longestCommonSubsequence(string s, string t) {
    int m = s.length(), n = t.size();
    vector<vector<int> > dp(m + 1, vector<int>(n + 1, 0));// size = (M + 1,N + 1);
    for (int i = 1; i <= m; ++i)
        for (int j = 1; j <= n; ++j)
            dp[i][j] = (s[i - 1] == t[j - 1])? dp[i - 1][j - 1] + 1 : max(dp[i - 1][j], dp[i][j - 1]);
        int len = dp[m][n];

        string lcs(len, " ");
    for (int i = m, j= n, index = len - 1; i > 0 && j > 0;)
    {
        if (s[i - 1] == t[j - 1]){
            lcs[index--] = s[i - 1];
            --i;
            --j;
        }
        else if (dp[i - 1][j] > dp[i][j - 1]) i--;
        else j--;
    }
    cout<<lcs<<endl;
    return len;
}

---

Another Complete code for C ++

#include <iostream>
using namespace std;
class solution
{
public:
    char *LCS_length(const char * x,const char * y)
    {
        int m=strlen(x);
        int n=strlen(y);
        int **c=new int*[m+1];
        int **b=new int*[m+1];
        for(int i=0;i<=m;++i)
        {
            c[i]=new int[n];
            b[i]=new int[n];
            for(int j=0;j<=n;++j)
            {
                c[i][j]=0;
                b[i][j]=0;
            }
        }
        int i=0,j=0;
        for(i=1;i<=m;++i)
        {
            for(j=1;j<=n;++j)
            {
                if(x[i]==y[j])
                {
                    c[i][j]=c[i-1][j-1]+1;
                    b[i][j]=1;              //diagnal
                }
                else {

                    if(c[i-1][j]>=c[i][j-1])
                        {
                            c[i][j]=c[i-1][j];
                            b[i][j]=2;          //up
                        }
                    else {
                        c[i][j]=c[i][j-1];
                        b[i][j]=3;              //left
                    }
                }
            }
        }
    int len = c[m][n];
    cout<<len<<endl;
    return print_LCS(b,x,m,n,len);
    }

char* print_LCS(int **b,const char* x,int i,int j,int len)  
    {
        cout<<x<<i<<j<<endl;
        char *t=new char[len];
        while(i!=0 || j!=0){
        if(b[i][j]==1)
        {   
            t[--len]=x[i-1];
            --i;
            --j;
        }
        else {
        if(b[i][j]==2)
                --i;
        else
            --j;
         }
        }
        return t;
    }
};
int main(int argc, char const *argv[])
{
    solution S;
    char *s=S.LCS_length("bdcaba","abcbdab");
    cout<<s;
    return 0;
}