与之前c语言版本相比主要是使用了STL容器.另外下标的计算方式也有改动:记录表c(矩阵)中第0行和第0列都初始化为0作为辅助.
因此第i行对应的是字符串x的第i-1个元素,与原图对比即明白:
这里写图片描述
由于string模板的限制,字符串从0下标开始,因此x[0]对应矩阵第1行.
明白这点,y亦同理.
#include <iostream>
#include <string>
#include <vector>
using namespace std;
int lcs(string s1, string s2) {
int len1 = s1.size();
int len2 = s2.size();
vector<vector<int>> c(len1+1, vector<int>(len2+1, 0));
for (int i = 1 ; i <= len1; i++) {
for(int j = 1; j <=len2 ; j++) {
if (s1[i-1] == s2[j-1]) c[i][j] = c[i - 1][j - 1] + 1;
else if (c[i - 1][j] >= c[i][j - 1]) c[i][j] = c[i - 1][j];
else c[i][j] = c[i][j - 1];
}
}
/* 输出调试
for (int i = 0 ; i <= len1; i++) {
for (int j = 0; j <= len2; j++) {
cout << c[i][j] << " ";
}
cout << endl;
}
*/
return c[len1][len2];
}
int main() {
string s1 = "aefawfawfawfaw";
string s2 = "aefawfeawfwafwaef";
cout << lcs(s1, s2); //输出:12
return 0;
}
