两个字符串的最长公共子序列（C++动态规划）

两个字符串的最长公共子序列（C++动态规划）

#include
using namespace std;

char a[200];
char b[200];
int f[201][201];//记录长度
char p[201][201];//记录公共字符

int m,n;

void LCS(){
	int i,j; 
	for(i=1;i<=m;i++){
		for(j=1;j<=n;j++){
			if(a[i-1] == b[j-1]){
				//左上方存放的一直是公共字符
				//通过左上方的值更新长度 
				//f[i][j]的值由f[i-1][j-1]更新; 
				f[i][j] = f[i-1][j-1]+1;
				p[i][j] = 1;//左上方 
			}
			else if(f[i][j-1] > f[i-1][j]){
				f[i][j] = f[i][j-1];
				p[i][j] = 2;//左方 
			}
			else{
				f[i][j] = f[i-1][j];
				p[i][j] = 3;//正上方 
			}
		}
	}
	printf("最长公共子序列长度为：%d",f[m][n]);
//遍历完成后f[m][n]存储的值为最大公共子序列长度 
}

//打印最长公共子序列 
void printLCS(){
	int i = m, j = n, k = f[m][n];
	char s[200];
	while(i > 0 && j > 0){
		if(p[i][j] == 1){
			s[k--] = a[i-1]; //i-1 从最后的一个元素开始逆序存入是s[]数组 
			i--; j--;
		}
		else if(p[i][j] ==2) j--;
		else i--;
	}
	printf("最长公共子序列为："); 
	for(int i=1;i<=f[m][n];i++)
		printf("%c",s[i]);
}






int main(){
	
	scanf("%s %s",&a,&b);
	m = strlen(a);
	n = strlen(b);
	LCS(); 
	printf("n");
	printLCS();
	return 0;
}

测试用例

asdfghjkl
agj