想要了解最长公共子序列首先要清楚这些概念：
<1>
子序列：
就是在原序列中找出一部分组成的序列。 例：字符串“abcdefg” 的子序列有 “ac”、“ade”....一共有2
7
个子序列
<2>
最长公共子序列：
一个序列 S ，如果分别是两个或多个已知序列的子序列，且是所有符合此条件序列中最长的，则 S 称为已知序列的最长公共子序列。
例：字符串“cnblogs”和“belong”的最长公共子序列为“blog”。
仔细想想我们可以发现其实最长公共子序列的个数不是唯一的，可能会有两个以上，
但是长度一定是唯一的，比如这里的最长公共子序列的长度为4。
<3>
子串：
串中任意个连续的字符组成的子序列称为该串的子串
<4>
最长公共子串：
两个字符串中，最长的相同子字符串的长度
最长公共子串（Longest Common Substirng）和最长公共子序列（Longest Common Subsequence，LCS）的
区别
为：
子串是串的一个连续的部分，子序列则是从不改变序列的顺序，而从序列中去掉任意的元素而获得新的序列；
也就是说，子串中字符的位置必须是连续的，子序列则可以不必连续。
最长公共子序列的
应用
：最长公共子序列是一个十分实用的问题，它可以描述两段文字之间的“相似度”，
即它们的雷同程度，从而能够用来辨别抄袭。对一段文字进行修改之后，
计算改动前后文字的最长公共子序列，将除此子序列外的部分提取出来，
这种方法判断修改的部分，往往十分准确。简而言之，百度知道、百度百科都用得上。
解决最长公共子序列问题
最好的选择 ---> “动态规划”
动态规划的计算两个序列的最长公共子序列的方法如下：
以两个序列 s1、s2 为例子：
设有二维数组x[i,j] 表示 s1 的 i 位和 s2 的 j 位之前的最长公共子序列的长度，则有：
x[1][1] = same(1,1);
x[i,j] = max{x[i-1][j -1] + same(i,j),x[i-1,j],x[i,j-1]}
其中，same(a,b)当 X 的第 a 位与 Y 的第 b 位相同时为“1”，否则为“0”。
此时，二维数组中最大的数便是 s1 和 s2 的最长公共子序列的长度，依据该数组回溯，便可找出最长公共子序列。
该算法的空间、时间复杂度均为O(n^2)，经过优化后，空间复杂度可为O(n)。
1 #include <stdio.h>
2 #include <string.h>
4 char s1[1000],s2[1000];
5 int x[1000][1000]; // 记录最长公共子序列
6 int y[1000][1000]; // 记录路径
7 int LCS()
9 int i,j;
10 int l1 = strlen(s1); // 计算字符串的长度
11 int l2 = strlen(s2);
12 memset(x,0,sizeof(x)); // 初始化 过滤掉0的情况
13 memset(y,0,sizeof(y));
15 for (i = 1; i <= l1; i ++)
16 {
17 for (j = 1; j <= l2; j ++)
18 {
19 if (s1[i-1] == s2[j-1]) // 相等的情况
20 { // 字符数组是从0开始的 所以这里要减 1
21 x[i][j] = x[i-1][j-1]+1;
22 y[i][j] = 1; // 记录路径
23 }
24 else if(x[i-1][j] >= x[i][j-1]) // 不相等的时候选择 比较“左边”和“上边”选择较大的
25 {
26 x[i][j] = x[i-1][j];
27 y[i][j] = 2; // 记录路径
28 }
29 else
30 {
31 x[i][j] = x[i][j-1];
32 y[i][j] = 3; // 记录路径
33 }
34 }
35 }
36 return x[l1][l2];
37 }
38 void print_LCS(int i,int j) // 根据标记路径的数组 输出最长公共子序列
39 {
40 if (i == 0 || j == 0)
41 return ;
42 if (y[i][j] == 1)
43 {
44 print_LCS(i-1,j-1);
45 printf("%c",s1[i-1]);
46 }
47 else if (y[i][j] == 2) // 左边
48 print_LCS(i-1,j);
49 else // 上边
50 print_LCS(i,j-1);
