最长公共子序列

 两个字符数组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;
    }
}