Problem Description
给出两个字符串A B，求A与B的最长公共子序列（子序列不要求是连续的）。 比如两个串为：
abcicba abdkscab
ab是两个串的子序列，abc也是，abca也是，其中abca是这两个字符串最长的子序列。
Input
第1行：字符串A 第2行：字符串B (A,B的长度 <= 1000)
Output
输出最长的子序列，如果有多个，随意输出1个。
Input示例
abcicba abdkscab
Output示例
abca
核心:
LCS(x,y) = (1) LCS(x - 1,y - 1) + 1 如果Ax ＝ By (2) max(LCS(x – 1, y) , LCS(x, y – 1)) 如果Ax ≠ By (3) 0 如果x = 0或者y = 0
#include<bits/stdc++.h> using namespace std; struct node { int x, y; }; int dp[1005][1005];//用来记录a字符串到i位，b字符串到j位最长公共子序列 node Pre[1005][1005];//保存路径 int main() { char a[1005], b[1005]; int len, len1, i, j; while(~scanf("%s %s", a, b)) { memset(dp, 0, sizeof(dp));//初始化 memset(Pre, 0, sizeof(Pre)); len = strlen(a); len1 = strlen(b); for(i = 1; i <= len; i++) { for(j = 1; j <= len1; j++) { if(a[i - 1] == b[j - 1])//如果相等，公共子序列加1 { dp[i][j] = dp[i - 1][j - 1] + 1; Pre[i][j].x = i - 1;//记录路径 Pre[i][j].y = j - 1; } else//dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) { if(dp[i - 1][j] > dp[i][j - 1]) { dp[i][j] = dp[i - 1][j]; Pre[i][j].x = i -1;//记录路径 Pre[i][j].y = j; } else { dp[i][j] = dp[i][j - 1]; Pre[i][j].x = i;//记录路径 Pre[i][j].y = j - 1; } } } } vector<char> q; i = len; j = len1; int num = dp[len][len1]; while(i && j) { int x = Pre[i][j].x, y = Pre[i][j].y; if(dp[x][y] == num - 1)//最长公共子序列长度变化的点。它的上一个位置是num - 1,它当前位置就是num，变化点记录下来 { num--; q.push_back(a[x]); } i = x; j = y; } for(i = q.size() - 1; i >= 0; i--)//输出 { printf("%c", q[i]); } printf("\n"); } return 0; }