问题描述： 这个问题其实很容易理解。就是给你两个序列X=｛x1,x2,x3......xm｝ Y=｛y1,y2,y3......ym｝，要求找出X和Y的一个最长的公共子序列。
例：Xi={A, B, C, B, D, A} Yj={B, C, A, B, A} 求得 Z={B, C, B, A}
问题详解： 那么问题来了，我们如何去求解出最终的过程呢？既然是复习周，那我就开门见山，直接用DP算法去解决这个问题。
分析：该问题具有最优子结构的性质。
这里我们使用上面的那个例子：我们此时倒着进行分析
①当我们知道了最长公共子序列为Z=｛B,C,B,A｝的时候，我们知道当取Xi序列的最后一个值x6=A与Yi序列的最后一个值Y5=A，此时X6=Y5，则z4=X6=Y5，就得出来的 Z1~Z3 为 X1~X5 与 Y1~Y4 的最长公共子序列。
②再往前走，X5=D而Y4=B我们知道 x5!=Y4 所以Z1~Z3是 X1~X5 与 Y1~Y3的子序列 或者是 X1~X4 与 Y1~Y4的子序列（这里这个例子是——Z｛B，C，B｝是A｛A，B，C，B｝与B｛B，C，A，B｝的公共子序列）
也许文字不太好理解，但是我们由此可以归纳出一个递推公式：
而C[i][j]中存的是序列X1~Xi与序列Y1~Yj的最长公共子序列长度。
下面我们来看具体的寻找方法——>
这里我们放一道例题：
给定两个序列为X=<A, B, C, B, D, A, B>和 Y=<B, D, C, A, B, A>，求最长公共子序列？
这个时候我们需要递归来填写出数组中的数字。
①我们来画出这个二维数组。
②因为0行0列并没有实际的意义，所以我们填上0。
③之后，我们开始递归写表。此时我们要知道，行数1~7代表X的各个数字，而列为Y的数字。当i=1是代表我拿出来X数列中的A，j=1代表我拿出来Y数列中的B。然后比较发现A!=B 所以我们判断max（C[0][1]，C[1][0]）--其实我们写算法的时候都默认从上面继承下来。发现都是0，所以C[1][1]=0。
④同样的情况一直到C[1][4]这个地方，此时我们发现X1=A，Y4=A。X1=Y4。所以我们调用C[i][j]=C[i-1][j-1]函数，从左上角继承下来。C[1][4]=C[0][3]=0+1=1。
。。。。。最后填写完成后为：
（其实算法思想很简单，就是当前两个数相同就左上角的值+1，不相同就比较左边和上面，找大的写上去）
此时我们就要进入下一步，就是根据这个表去找到最长公共子序列。
而在上面的每一步填写表格的时候，我们需要加上一步——就是记录我当前的这个格子的值是从什么位置继承来的。（创建一个新的二维数组） 这里我们规定：
①当C[i][j]是从左上角+1得来的，我们在b[i][j]处填上1。
②当C[i][j]是从左侧继承来的，b[i][j]=3。
③当C[i][j]从上面继承来的，b[i][j]=2。
我们这里得到b[i][j]
之后我们从最右下角的位置开始，根据b中的表格得到：
这个时候我们取箭头的末端所在行——第2、3、4、6行，对应X序列中的B，C，B，A。由此得到Z序列。
算法代码：
因为这道题目要考上机题，所以我在这里把代码思想也放到这里，不过代码很简单这里就不详细叙述了
#include<iostream>
#include<string.h>
using namespace std;
int C[][];
int bb[][];
char A[];
int LCS(char a[],char b[],int a_len,int b_len){
for(int i =;i<;i++){
C[][i]=;
C[i][]=;
}
for(int h=;h<=a_len;h++){
for(int hh=;hh<=b_len;hh++){
if(a[h-]==b[hh-]) {
C[h][hh]=C[h-][hh-]+;
bb[h][hh]=;
}
else{
if(C[h-][hh]>=C[h][hh-]) {
C[h][hh]=C[h-][hh];
bb[h][hh]=; }
if(C[h-][hh]<C[h][hh-]){
C[h][hh]=C[h][hh-];
bb[h][hh]=;
}
}
}
}
}
int LCScout(int a,int b){
if(a==||b==) return ;
else{
if(bb[a][b]==) {
LCScout(a-,b-);
cout<<A[a-];
}
if(bb[a][b]==){
LCScout(a-,b);
}
if(bb[a][b]==){
LCScout(a,b-);
}
}
}
int main(){ char B[];
cin>>A;
cin>>B;
int A_len = strlen(A);
int B_len = strlen(B);
LCS(A,B,A_len,B_len);
LCScout(A_len,B_len); }
上面的代码是我自己写着玩的一些寻找最长公共序列的方法，下面我在放上计蒜课上的——《最长共公子串》
#include<iostream>
#include<string.h>
using namespace std;
int lcs[][];
int b[][]; int LCS(char A[],char B[],int a_len,int b_len){
int max=;
for(int i=;i<=;i++){
lcs[][i]=;
lcs[i][]=;
}
for(int i=;i<=a_len;i++){
for(int h=;h<=b_len;h++){
if(A[i-]==B[h-]) {
lcs[i][h]=lcs[i-][h-]+;
if(lcs[i][h]>max) max=lcs[i][h];
b[i][h]=;
}
else{
if(lcs[i-][h]>=lcs[i][h-]){
lcs[i][h]=lcs[i-][h];
b[i][h]=;
}
else{
lcs[i][h]=lcs[i][h-];
b[i][h]=;
}
}
}
}
return max;
}
int main(){
char A[];
char B[];
cin>>A;
cin>>B;
int A_len = strlen(A);
int B_len = strlen(B); cout<<LCS(A,B,A_len,B_len);
}
是不是很基础~相信大家算法考试应该问题不大~加油加油！
——————————————————————————————————————Made By Pinging