最长公共子序列和最长公共子串区别
最长公共子串（Longest Common Substring）与最长公共子序列（Longest Common Subsequence）的区别：
子串要求在原字符串中是连续的，而子序列则只需保持相对顺序一致，并不要求连续。
例如 X = {a, Q, 1, 1}; Y = {a, 1, 1, d, f}
那么，{a, 1, 1}是X和Y的最长公共子序列，但不是它们的最长公共字串。
最优子结构
思路
我们的目的是寻找两个顺序相对一致的序列
所以我们需要构建一个二维数组进行统计，记录遍历的时候他们相同的地方
设有这样的两个序列:
{A,L,C,H,E,M,I,S,T}
{A,L,G,O,R,I,T,H,M,S}
第一行的意思可以看作空和空.空和A。。。的最长子序列都为0
从第二行开始，如果相同就将左上角的值复制加一填入，所以这里就填上 1（0+1）
到第三个，元素不同的话就将这个位置的左和上元素比较，填入最大的，这里上是0左是1，所以填入1；
以此类推
到了第二行，第二行与第二列元素一样，就读取左上角元素的复制后加一填入，1加1填入2
之后都是以此类推，最后得到了
通过以上的分解后，我们可以得到这样一个状态转移方程
if(a===b){ //如果他们相同
table[row][col] = table[row - 1][co1 - 1] + 1; //我们找到他斜上角的那个值进行加一之后赋值
} else {
table[row][col] = Math. max(table[row][col - 1]， table[row - 1][col]);//如果不相同，我们就填入元素上方和左边最大的元素
}
整理后的代码为
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<string.h>
int len[100][100]; //最大子序列的生成矩阵
int dis[100][100]; //创建数组dis[][]来储存每一次的信息，如果xi=yj则为1，另外两种情况为dis[][]中储存为2,3；如1代表两个都是，2代表行是左，3代表列是上
char A[100] = "ABCBDAB";
char B[100] = "BDCABA";
void show(int, int);
int main()
{
int n = strlen(A);
int m = strlen(B);
printf("%d %d\n", n, m);//输出两个序列的长度
int i, j, k;
for (i = 0; i <= n; i++)
len[i][0] = 0; //让列为0
for (i = 0; i <= m; i++)
len[0][i] = 0; //让第一行为0
for (i = 1; i <= n; i++){
for (j = 1; j <= m; j++){
if (A[i-1] == B[j-1]){ //若他们相等，则让他等于左上角的元素加1
len[i][j] = len[i - 1][j - 1] + 1;
dis[i][j] = 1; //记录下来在这里是相等的，标记为1
}
else if (len[i - 1][j] >= len[i][j - 1]){ //他们不相等的时候，取上和左元素最大的那个
len[i][j] = len[i - 1][j];
dis[i][j] = 3; //取上标记为3
}else{
len[i][j] = len[i][j - 1];
dis[i][j] = 2; //取左标记为2
}
}
}
printf("最大子序列长度：%d ", len[n][m]); //最后的一个按直接的结果，他的值就是最长的序列数
for (i = 0; i <= n; i++){
for (j = 0; j <= m; j++){
printf("%d ", dis[i][j]);
}
puts("");
}
puts("子序列为：");
show(n, m);
}
void show(int i, int j){
if (i == 0 || j == 0)
return;
if (dis[i][j] == 1){
show(i - 1, j - 1);
printf("%c ", A[i-1]);
}
else if (dis[i][j] == 3){
show(i - 1, j);
}else{
show(i, j - 1);
}
}
标签：show,int,len,公共,序列,100,最长,dis From： https://www.cnblogs.com/kuailest/p/16871777.html