Longest Common Subsequence最长公共子序列：
每个dp位置表示的是第i、j个字母的最长公共子序列
class Solution {
public:
int findLength(vector<int>& A, vector<int>& B) {
int len1 = A.size();
int len2 = B.size();
if(len1 == || len2 == )
return ;
vector<vector<int>> result(len1+,vector<int>(len2+));
for(int i = ;i <= len1;i++){ //第一行第一列都为0，因为第一行第一列都没有字符串
result[i][] = ;
}
for(int i = ;i <= len2;i++){
result[][i] = ;
}
for(int i = ;i <= len1;i++){
for(int j = ;j <= len2;j++){
if(A[i-] == B[j-])
result[i][j] = result[i-][j-] + ;
else
result[i][j] = max(result[i-][j],result[i][j-]);
}
}
return result[len1][len2];
}
};
Longest Common Substring最长公共子串
每个dp代表以i、j这个坐标的最长公共子串，所以求最终的要遍历所有的
class Solution {
public:
int findLength(vector<int>& A, vector<int>& B) {
int len1 = A.size();
int len2 = B.size();
if(len1 == || len2 == )
return ;
vector<vector<int>> result(len1+,vector<int>(len2+));
for(int i = ;i <= len1;i++){ //第一行第一列都为0
result[i][] = ;
}
for(int i = ;i <= len2;i++){
result[][i] = ;
}
for(int i = ;i <= len1;i++){
for(int j = ;j <= len2;j++){
if(A[i-] == B[j-])
result[i][j] = result[i-][j-] + ;
else
result[i][j] = ;
}
}
int maxnum = 0x80000000;
for(int i = ;i <= len1;i++){
for(int j = ;j <= len2;j++){
if(result[i][j] > maxnum)
maxnum = result[i][j];
}
}
return maxnum;
}
};
更简洁的一种写法：
class Solution {
public:
/**
* @param A: A string
* @param B: A string
* @return: the length of the longest common substring.
*/
int longestCommonSubstring(string &A, string &B) {
// write your code here
int m = A.size();
int n = B.size();
vector<vector<int> > dp(m+,vector<int>(n+));
for(int i = ;i <= m;i++)
dp[i][] = ;
for(int i = ;i <= n;i++)
dp[][i] = ;
int max_num = ;
for(int i = ;i <= m;i++){
for(int j = ;j <= n;j++){
if(A[i-] == B[j-]){
dp[i][j] = dp[i-][j-] + ;
max_num = max(max_num,dp[i][j]);
}
else
dp[i][j] = ;
}
}
return max_num;
}
};
相同：都要建立m+1，n+1的二维数组
区别：1. 最长公共子串要求连续的，最长公共子序列可以不连续，所以dp的递推公式第二项不同
2. 最长公共子序列最后一个值就是最长，最长公共子串要比较哪个位置最长