编辑代码

#include<iostream>
using namespace std;
#include<string>
#include<vector>
int lcs(string s, string t) {
 int slen = s.size();
 int tlen = s.size();
 int i = 0, j = 0;
 vector<int> col(slen + 1, 0);
 vector<vector<int>>arr(tlen + 1, col);
 for (int i = 1; i <=slen; i++) {
  for (int j = 1; j <=tlen; j++) {
   if (s[i-1] == t[j-1]) {
    arr[i][j] = arr[i - 1][j - 1] + 1;
   }
   else
   {
    arr[i][j] = (arr[i - 1][j]) > (arr[i][j - 1]) ? arr[i - 1][j] : arr[i][j - 1];
   }
  }
 }
 return arr[slen][tlen];
}
int main() {
 string s = "ABCDEFG";
 string t = "ABCJEFG";
 int len = lcs(s, t);
 cout << "最长公共子序列长度为：" << len << endl; 
 return 0;
 system("pause");
 return 0;
}