给两个字符串，求出最长公共子序列，输出字符串。
//得到公共长度二维数组 void longest_seq(string str1,string str2,vector<vector<int>>& dp) { int m = str1.size(),n = str2.size(); //vector<vector<int>> dp(m,vector<int>(n,0)); string res = ""; for (int j = 0; j < n; j++) { if (str2[j] == str1[0]) { dp[0][j] = 1; res += str2[j]; } if (j >= 1 && dp[0][j-1] == 1) dp[0][j] = 1; } for (int i = 1; i < m; i++) { if (str1[i] == str2[0]) { dp[i][0] = 1; } if (i >= 1 && dp[i-1][0] == 1) dp[i][0] = 1; } for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { if (str1[i] == str2[j]) dp[i][j] = dp[i-1][j-1]+1; else dp[i][j] = max(dp[i-1][j],dp[i][j-1]); } } // return dp; } //得到字符串 string longest_str(string s1,string s2,vector<vector<int>> dp) { int m = s1.size(),n = s2.size(); string res = ""; int i = m - 1,j = n - 1; while (i >= 0 && j >= 0) { if ((i > 0) && dp[i][j] == dp[i-1][j]) i--; else if((j > 0) && dp[i][j] == dp[i][j-1]) j--; else { res = s1[i] + res; i--; j--; } } return res; }如果只是需要最长公共序列长度，只需要第一个函数就可以了，而且可以压缩空间只用一位数组做。第二个函数是搜寻找到序列。
这个和公共子序列不同，这个是连续的字符串。记录最大值和最大值字符串位置就可以得到字符串结果，不只是长度值。
方法1：DP。空间和时间复杂度都是O(MN)
string longest_substr(string str1,string str2){ string res = ""; int m = str1.size(),n = str2.size(); vector<vector<int>> dp(m,vector<int>(n,0)); int max_len = 0; int max_loc2 = 0;//str2的位置 for (int j = 0; j < n; j++) { if (str2[j] == str1[0]) { dp[0][j] = 1; max_len = 1; max_loc2 = j; } } for (int i = 0; i < m; i++) { if (str1[i] == str2[0]) { dp[i][0] = 1; max_len = 1; max_loc2 = 0; } } for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { if (str1[i] == str2[j]) { dp[i][j] = dp[i-1][j-1] + 1; } if (dp[i][j] > max_len) { max_len = dp[i][j]; max_loc2 = j; } } } for (int j = max_loc2; j > max_loc2 - max_len; j--) { res = str2[j] + res; } return res; }方法2：空间复杂度为O（1）
//todo这里不同于一般编辑距离，这里增加，删除，替换代价分别为ic,dc,rc.
int distance(string s1,string s2,int ic,int dc,int rc) { int m = s1.size(),n = s2.size(); if (m == 0) return n * dc; if (n == 0) return n * ic; vector<vector<int>> dp(m+1,vector<int>(n+1,0)); for (int i = 1;i <= m; i++) { dp[i][0] = ic * i; } for (int j = 1; j <= n; j++) { dp[0][j] = j * dc; } for (int i = 1; i <= m; i++) { for (int j = 1; j <=n; j++) { if (s1[i-1] == s2[j-1]) { dp[i][j] = dp[i-1][j-1]; } else { dp[i][j] = min(dp[i-1][j] + ic,min(dp[i][j-1]+dc,dp[i-1][j-1]+rc)); } } } return dp[m][n]; }方法2：压缩空间方法，和简单的压缩空间稍微有些不一样。
int distance（）