状压dp, 用二维数组dp[n1 + 1][n2 + 1] 记录所有可能的[匹配态]对应的截至当前字符的公共子串的长度；

为了不单独考虑初始边界的更新状态，增加dp[0][0] 用作初始化开始边界，即： dp[0][0] = 0;

1. 利用dp[i][j]记录以str1[i - 1] 与 str2[j -1] 为共同尾字符 的最长公共子串的长度；

其中初值 i = 1 ， j =1；

2. 枚举str1 每个字符 关于str2每个字符配对的状态，其更新公式为：

• 如果 (str[i - 1] == str2[j - 1]) ，则当前最长子串 = 上一状态的最长有效子串 + 新的共同字符：

  

• 如果 (str[i - 1] != str2[j - 1]) ，则当前最长子串 = 0：

  

3. 每次搜索都更新当前最大公共子串的状态：

• 长度: Max，

• 以及其对应于str1或者str2字符串的结束位置: pos = i - 1 或者 pos = j - 1；

  4最后截取长度为：Max,开始位置为: pos - Max + 1 的字串即满足要求；

C++实现代码如下

    string LCS(string str1, string str2) {
        // write code here
        int len1 = str1.size();
        int len2 = str2.size();
        int max = 0, pos = 0;
        vector<vector<int>> dp(len1 + 1, vector<int> (len2 +1 , 0));
        for (int i = 1; i <= len1; ++i) {
            for (int j = 1; j <= len2; ++j) {
                if (str1[i - 1] == str2[ j - 1]) {
                    dp[i][j] =  dp[i - 1][j - 1] + 1;
                    if (max < dp[i][j]) {
                        max = dp[i][j];
                        pos = j - 1; // i - 1
                    }
                }
                else {
                    dp[i][j] = 0;
                }

            }
        }
        return  str2.substr(pos - max + 1, max);
    }