前言

LCS可以描述两段文字之间的“相似度”，即它们的雷同程度，从而能够用来辨别抄袭。另一方面，对一段文字进行修改之后，计算改动前后文字的最长公共子序列，将除此子序列外的部分提取出来，这种方法判断修改的部分，往往十分准确。

算法介绍

子序列：一个序列S任意删除若干个字符得到新序列T。

公共子序列：两个序列X和Y中都存在的项组成的序列。

最长公共子序列：两个序列X和Y的公共子序列中最长的序列。

例如：

字符串13455与245576的最长公共子序列为455

字符串acdfg与adfc的最长公共子序列为adf

 求取算法详解

第一种：自定义暴力求取方式

假定字符串X，Y的长度分别为m，n

X的一个子序列即下标序列{1, 2, …, m}的严格递增子序列，因此，X共有2m个不同子序列；同理，Y有2n个不同子序列，从而穷举搜索法需要指数时间O(2m*2n)；

对X的每一个子序列，检查它是否也是Y的子序列，从而确定它是否为X和Y的公共子序列，并且在检查过程中选出最长的公共子序列；

显然，不可取。

针对该种算法进行改良，只对第一组数据进行依次列出，然后与第二组进行比较。其时间复杂度虽然也很高，但与2m*2n相比还是要少一些。

void lscChangeViolence(int *X, int *Y, int m) { int *AllX, *AllFlag, *result; AllX = (int*)malloc(sizeof(int)*m); AllFlag = (int*)malloc(sizeof(int)*m); result = (int*)malloc(sizeof(int)*m); for (int i = 0; i < m; i++) { AllX[i] = 0; AllFlag[i] = 0; result[i] = -1000; } int count = 1; while (count < pow(2, m)) { int num = 0; // 按照取某一位的值和不取某一位的值，将X中的某些值赋值给AllX for (int i = 0; i < m; i++) { if (((count >> i) & 1) == 1) { AllX[num] = X[i]; num++; } } // 给定比较数组 int *compare; compare = (int*)malloc(sizeof(int)*(num)); for (int i = 0; i < num; i++) { compare[i] = AllX[i]; } int comNum = 0; int jump = 0; int maxNum = -1; int start = 0; // 如果子数组与第二组匹配上，则记录长度，并记下数据 for (int i = 0; i < num; i++) { if (start > n) { break; } for (int j = start; j < n; j++) { if (compare[i] == Y[j]) { start = j + 1; comNum++; break; } } if (comNum == i) { break; } } if (comNum > maxNum) { maxNum = comNum; for (int k = 0; k < maxNum; k++) { result[k] = compare[k]; } } count++; } for (int i = 0; i < 5; i++) { if (result[i] != -1000) { printf("result[%d]=%d\n", i, result[i]); } } }

第二种：动态规划法

字符串X，长度为m，从1开始数；

字符串Y，长度为n ，从1开始数；

LCS(X , Y) 为字符串X和Y的最长公共子序列。

若xm=yn(最后一个字符相同)，则：Xm与Yn的最长公共子序列Zk的最后一个字符必定为xm或yn。

LCS(Xm , Yn) = LCS(Xm-1 , Yn-1) + xm

若xm≠yn，则：要么LCS(Xm,Yn)=LCS(Xm-1, Yn)，要么LCS(Xm,Yn)=LCS(Xm, Yn-1)。

则：

   

使用二维数组C[m,n]。

c[i,j]记录序列Xi和Yj的最长公共子序列的长度。

当i=0或j=0时，空序列是Xi和Yj的最长公共子序列，故c[i,j]=0。

使用二维数据B[m,n]，其中，b[i,j]标记c[i,j]的值是由哪一个子问题的解达到的。即c[i,j]是由c[i-1,j-1]+1或者c[i-1,j]或者c[i,j-1]的哪一个得到的。取值范围为Left，Top，LeftTop三种情况。  

// 根据规则将c[i][j]进行赋值，获取方向数组b[i][j] void lcs_length(char *X, char *Y, int mLength, int nLength,int **C,char **B) { int num = 0; for (int i = 1; i < mLength + 1; i++) { for (int j = 1; j < nLength + 1; j++) { if (X[i-1] == Y[j-1]) { C[i][j] = C[i - 1][j - 1] + 1; B[i][j] = 'x'; } else if (C[i - 1][j] >= C[i][j - 1]) { C[i][j] = C[i - 1][j]; B[i][j] = 's'; } else { C[i][j] = C[i][j - 1]; B[i][j] = 'z'; } } } for (int i = 0; i < mLength + 1; i++) { for (int j = 0; j < nLength + 1; j++) { printf("C[%d][%d]=%d ", i, j, C[i][j]); } printf("\n"); } }

下面打印最长公共子序列

// 从最后的位置进行索引，按照方向依次寻找数据，将标记为x的数据打印即为最长子数组 void lcsPrint(char **B, char *X, int i, int j) { if (i == 0 || j == 0) { return; } if (B[i][j] == 'x') { lcsPrint(B, X, i - 1, j - 1); printf("X[%d]=%c\n", i - 1, X[i - 1]); } else if (B[i][j] == 's') { lcsPrint(B, X, i - 1, j); } else { lcsPrint(B, X, i, j - 1); } }

参考资料：

七月算法： https://www.julyedu.com/