最长公共子序列
两个字符数组a和b,dp数组存放到从a[1]b[1](即第一个元素)到a[i],b[j]为止最大的公共元素数目
dp[i][j] = dp[i-1][j-1] + 1 如果a[i] == b[j];
=max(dp[i][j-1] , dp[i-1][j]) a[i] ≠ b[j]
用c标记方便输出公共子序列。
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e3 + 5;
char a[maxn], b[maxn];
int c[maxn][maxn];//标记数组
int dp[maxn][maxn];
int la,lb;
void lcs(){
for(int i = 1; i <= la; i++){
for(int j = 1; j <= lb; j++){
if(a[i] == b[j]){
dp[i][j] = dp[i-1][j-1] + 1;
c[i][j] = 1;//来自左上方
}
else if(dp[i-1][j] >= dp[i][j-1]){
dp[i][j] = dp[i-1][j];
c[i][j] = 2;//来自上方
}
else if(dp[i][j-1] > dp[i-1][j]){
dp[i][j] = dp[i][j-1];
c[i][j] = 3;//来自左方
}
}
}
}
void print(int x, int y){
if(x == 0 || y == 0)return;
if(c[x][y] == 1) {
print(x-1, y-1);//来自左上方所以递归左上方
printf("%c", a[x]);//保证正序输出,若想逆序输出只需把输出调到print()之前即可
}
else if(c[x][y] == 2)
print(x-1, y);//来自上方所以递归上方
else print(x, y-1);//来自左方所以递归左方
}
int main()
{
printf("请输入两个序列直到文件末尾\n");
while(~scanf("%s%s", a+1, b+1)){//从a[1],b[1]开始输入
memset(dp, 0, sizeof dp);
memset(c, 0, sizeof c);
la = strlen(a+1), lb = strlen(b+1);//从a[1],b[1]开始判断长度
lcs();//求最长公共子序列
printf("最长公共子序列长度为%d\n公共子序列是:\n", dp[la][lb]);//最长公共子序列的值
print(la, lb);//输出函数
cout << endl << endl;
}
}