实验目的
1、了解串的基本概念
2、掌握求最长公共子序列的算法
- 实验内容和代码
设计并实现，求最长公共子序列的算法。使用动态规划算法解决最长公共子序列问题：给定两个序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}，找出X和Y的最长公共子序列。（使用动态规划的思想）（递归）
#include<iostream>
#include<stack>
#include<string>
#include<cstring>
using namespace std;
void GetLCS(string &str1, string &str2){
int m = str1.length() + 1;
int n = str2.length() + 1;
int length[m][n];
int state[m][n];
memset( state, 100, sizeof(state) );//初始化函数，将全部内容设定为指定的值
for(int i=0; i<m; i++){ //初始化第1列
length[i][0] = 0;
}
for(int j=0; j<n; j++){//初始化第1行
length[0][j] = 0;
}
for(int i=1; i<m; i++){
for(int j=1; j<n; j++){
if(str1[i-1] == str2[j-1]) {
length[i][j] = length[i-1][j-1] + 1;
state[i][j] = 0;
}else if(length[i][j-1] >= length[i-1][j]) {
length[i][j] = length[i][j-1];
state[i][j] = -1; //列数减一
}else {
length[i][j] = length[i-1][j];
state[i][j] = 1; //行数减一
}
}
}
//打印最长子序列
stack<char> lcs;//常用栈函数，栈的一些基本操作包括在stack文件中
for(int i=m-1, j=n-1; i>=0 && j>=0;){
if(state[i][j] == 0){//说明str1的第i个元素和str2的第j个元素相同
lcs.push(str1[i-1]);
i--;
j--;
}else if(state[i][j] == 1){
i--; //行数减一
}else{
j--; //列数减一
}
}
if(lcs.empty()){
cout<<"没有公共子序列"<<endl;
return ;
}
cout<<"最长的子序列：";
while(!lcs.empty()){
cout<<lcs.top();
lcs.pop();
}
cout<<"\n其长度为："<<length[m-1][n-1];
return ;
}
int main(){
string str1 = "abcdefghijklmnree";
string str2 = "cdfgrrze";
cout<<"序列1："<<str1<<endl;
cout<<"序列2："<<str2<<endl;
GetLCS(str1,str2);
return 0;
}
- 实验小结
编辑
memset（）函数是初始化函数，作用是将某一块内存中的全部内容设置为指定的值
序列1和序列2最大公共子序列有三种：BCAB、BDAB、BCBA，只能输出BDAB的情形
四、教师评语
