问题描述

给定两个字符串,求其最大公共子序列

问题分析

本题是典型的动态规划问题,我们将大字符串分解成小字符串进行计算。

为了节省空间,我们使用一维滚动数组求解

算法设计

  1. 找到递推入口:当len(string_first) = 0 时, 一维数组元素均为零。

    当len(string_second) = 0时,一维数组元素均为零

  2. 从字符串二长度为一开始,设置二层循环,对记录的一维数组进行修改

  3. 递归公式

    若str1[i] == str2[j] , 则v[j] = tmp (tmp单独保存斜上角的数)

    若str1[i] != str2[j] , 则v[j] = max(v[j],v[j-1])

  4. 总时间复杂度 = O(len(str1) *len(str2)) 约等于 O(n^2)

参考代码

#include <bits/stdc++.h>
using namespace std;
int main(int argc, char const *argv[])
{
//文件操作
ifstream in("Common_subsequence.txt");
if(!in) { cout << "打开文件出错" << endl; return 0 ; }
string str1 , str2 ;
getline(in,str1);
getline(in,str2);
int len1 = str1.size() , len2 = str2.size();
int arrays = max(len1,len2);
str1 = '0' + str1;
str2 = '0' + str2;
vector<int> v(arrays+1);
int row = arrays,col = 0 ;
string stemp ;
if(len1 >= len2) {col = len2; stemp = str2 ; str2 = str1; str1 = stemp ;}
else{col = len1 ;}
int temp = 0 , tmp = 0 ;

for(int i = 1 ; i <= col ; ++i){
tmp = 0 ;
for(int j = 1 ; j <= arrays ; ++j){
temp = v[j];
if(str1[i] == str2[j]){v[j] = tmp + 1;}
else{v[j] = max(v[j-1],v[j]);}
tmp = temp ;
}
//输入每一行值
for(int i = 0 ; i <= arrays ; ++i){cout << v[i] << " ";}
cout<<endl;
}
//输入字符串一
str1 = str1.substr(1,str1.size()-1);
str2 = str2.substr(1,str2.size()-1);
cout << "str1: "<<str1<<endl;
//输入字符串二
cout << "str2: "<<str2<<endl;
return 0;
}

谢谢访问