最长公共子序列

最长公共子序列的问题很简单，就是在两个字符串中找到最长的子序列，这里明确两个含义：

子串：表示连续的一串字符 。子序列：表示不连续的一串字符。

所以这里要查找的是不连续的最长子序列，

动态规划

这里为什么要使用动态规划可以说一下，简单来说动态规划是为了降低时间复杂度的一种算法，申请一个额外空间，来保存每一个步骤的结果，最后从这些结果中找到最优的解。

这里有个问题就是：一般来说，当前的最优解，只与当前时刻和上一时刻有关系，和其他时刻没有关系，这样才能让动态规划发生作用，降低复杂度。

分析LCS

其实LCS看起来很麻烦，找不到思路，如果暴力破解可能要O(n^4)了，而这个题目使用动态规划的思想也非常简单，为何相比之前的问题不好找思路呢？

是因为之前的动态规划问题例如：背包问题，生产线问题，都是一维数组空间内的结果，规划到一个线性时间内，而这个题目需要O(m*n)的时间复杂度和空间复杂度。

所以其实就是进行m*n次对比，每次保存当前的最优解，就可以了。

代码实现分析

这里有个问题，就是我们需要的结果仅仅是长度？ 还是包括这个序列串一起输出。

看下面图：

这里可以看到，我们构造的一个i*j的矩阵，这个矩阵里的内容不但包括数值（当前结果的最优解），还包括一个方向箭头，这个代表了我们回溯的时候，需要行走的方向。

所以我们这里保存两个值，可以使用两个二维矩阵，也可以使用一个结构体矩阵。

解法分析

其实这个题目在动态规划来理解，也非常简单。一个状态转移函数。

这个非常好理解，其中一个字符串为0的时候，那么肯定是0了。

当两个字符相等的时候，这个时候很好理解，举例来说：

abcd和adcd,在遍历c的时候，发现前面只有a相等了，也就是1.

那么c相等，也就是abc和adc在匹配的时候，一定比ab和ad的长度大1，这个1就是c相等么。也就是相等的时候，是比c[i-1][j-1]大1的。

下一个更好理解了，如果不相等，肯定就是找到上一个时刻对比最大的么。

代码

这个代码只输出了LCS的长度，而结果数组的方向我已经存储好了，想要遍历的，直接从后向前遍历数组就可以输出最长公共子序列了，即哪些 direct = 0 的节点。

//// main.cpp// LCS//// 最长公共子序列(LCS)//#include <iostream>using namespace std;/** 这里可以不定义长度，输入的字符串用string存储，然后利用string.c_str()来对字符串进行数组转化。 我这里为了方便没有这样做。*/#ifndef MAX_LENGTH#define MAX_LENGTH 15 //定义字符串最大长度#endifint MaxNum(int firstNum, int secondNum){return firstNum > secondNum ? firstNum : secondNum;}//定义数组结构体struct matrix{int num;int direct;};typedef matrix Matrix;int LCS(char *strA, char *strB, int lengthA, int lengthB, Matrix *resultMatrix[]){if (lengthA == 0 || lengthB == 0) {return 0;}for (int i = 0; i < lengthA; i++) {for (int j = 0; j < lengthB; j++) {resultMatrix[i][j].num = 0; //设置所有默认的最长为0resultMatrix[i][j].direct = 1; //所有默认方向变成上 0斜上，1上，-1左}}for (int i = 0; i < lengthA; i++) {for (int j = 0; j < lengthB; j++) {if (strA[i] == strB[j]) {resultMatrix[i+1][j+1].num = resultMatrix[i][j].num + 1;resultMatrix[i+1][j+1].direct = 0;}else{resultMatrix[i+1][j+1].num = MaxNum(resultMatrix[i+1][j].num, resultMatrix[i][j+1].num);resultMatrix[i+1][j+1].direct = resultMatrix[i+1][j].num > resultMatrix[i][j+1].num ? 1 : -1;}}}return resultMatrix[lengthA][lengthB].num;}int main(int argc, const char * argv[]) {char *strA = (char*)malloc(sizeof(char) * MAX_LENGTH);char *strB = (char*)malloc(sizeof(char) * MAX_LENGTH);scanf("%s",strA);scanf("%s",strB);int lengthA = (int)strlen(strA);int lengthB = (int)strlen(strB);Matrix *resultMatrix[lengthA+1];for (int i = 0; i <= lengthA; i++) {resultMatrix[i] = (Matrix*)malloc(sizeof(struct matrix)* (lengthB+1));}int max = LCS(strA, strB, lengthA, lengthB, resultMatrix);printf("%d\n",max);std::cout << "Hello, World!\n";return 0;}

上面我们介绍了最长公共子序列，下面我们来介绍一种子串（连续字符）的模式匹配问题，以及 BF 算法和 KMP 算法。

KMP 算法背景

给定一个主串（以 S 代替）和模式串（以 P 代替），要求找出 P 在 S 中出现的位置，此即串的模式匹配问题。

Knuth-Morris-Pratt 算法（简称 KMP）是解决这一问题的常用算法之一，这个算法是由高德纳（Donald Ervin Knuth）和沃恩·普拉特在 1974 年构思，同年詹姆斯·H·莫里斯也独立地设计出该算法，最终三人于 1977 年联合发表。

在继续下面的内容之前，有必要在这里介绍下两个概念：真前缀和真后缀。

由上图所得， "真前缀" 指除了自身以外，一个字符串的全部头部组合；"真后缀" 指除了自身以外，一个字符串的全部尾部组合。于是得到两个集合，而我们后面的 next 数组的元素便是这两个集合之交中最长字符串元素的长度。而 KMP 算法便是根据next数组中的值来减少回溯重复比较字符而提高算法的效率的。

暴力朴素字符串匹配BF 算法

初遇串的模式匹配问题，我们脑海中的第一反应，就是朴素字符串匹配BF(Brute Force)（即所谓的暴力匹配），代码如下：

/* 字符串下标始于 0 */int strFind(const char *str, const char *substr){assert(str != NULL && substr != NULL);int m = strlen(str), n = strlen(substr);if(m < n) return -1for(int i=0; i <= m-n; ++i){for(int j=0; j < n; ++j){if(str[i+j] != substr[j])break;}if(j == n) // 匹配成功return i;}return -1;}

暴力匹配的时间复杂度为O( (m-n+1) * n)，其中n为 S 的长度，m为 P 的长度。很明显，这样的时间复杂度很难满足我们的需求。

接下来进入正题：时间复杂度为Θ(n+m)的 KMP 算法。

KMP字符串匹配算法

简言之，以图中的例子来说，在 i 处失配，那么主字符串和模式字符串的前边6位就是相同的。又因为模式字符串的前6位，在前 6 位中我们发现其"真前缀" 和 "真后缀" 的最长的相同真前后缀的长度是 4，它的前4位前缀和后4位后缀是相同的，所以我们推知主字符串i之前的4位和模式字符串开头的4位是相同的。就是图中的灰色部分。那这部分就不用再比较了。而当我们回溯时，此时 i = 6，j = 4，我们保持 i = 6, 不变。而将模式串向右滑动，即调整 j 的值，而凑巧我们知道其 next[ i=4 ] 此时的值，代表最长的相同真前后缀长度，就等于 4。于是我们果断将 j 更新回溯为 j = 4, i 不变，i = 6。得到如图（b）的状态。

有了上面的分析，我们先假设已经有了获取 next 数组的函数，在不分析其具体实现的抽象之上便可以构建起 KMP 算法的框架，如下：

/* 在 S 中找到 P 第一次出现的位置 */int KMP(string S, string P, int *next){GetNext(P, next);int i = 0; // S 的下标int j = 0; // P 的下标int s_len = S.size();int p_len = P.size();while (i < s_len && j < p_len) // 因为末尾 '\0' 的存在，所以不会越界{if (j == -1 || S[i] == P[j]) // P 的第一个字符不匹配或 S[i] == P[j]{++i; ++j;}elsej = next[j]; // 当前字符匹配失败，进行跳转}if (j == p_len) // 匹配成功return i - j;return -1;}

注意，因为作为模式串如果只有一个字符，则它肯定没有其相等的最长真前后缀。故我们会将 next [0] = -1 即第一位的值设为 -1。所以在上述的代码中 if 条件中的表达式 j == -1 是有可能通过 else 语句中的 next[j] 赋值而致使其成立的。此时表示其第一个字符不匹配。注意，每一个 next[j] 的值都是依赖从模式串中的 [0 ... j-1] 中的相等的最长真前后缀的长度决定的。

于是我们便可以的出求取 next 数组的第一种方法：

/* P 为模式串，下标从 0 开始 */void GetNext(string P, int *next){int p_len = P.size();int i = 0; // P 的下标int j = -1; next[0] = -1;while (i < p_len){if (j == -1 || P[i] == P[j]){++i;++j;next[i] = j;}elsej = next[j];}}

KMP优化

其实在上面的求取 next 数组中，在 ++i, ++j 之后并没有判断 p[i] 是否与 p[j] 相同，故仍会出现有冗余的比较字符的情况，于是就有了下面的求取 next 数组的改进算法。使用这种方式求取的 next 数组，整合到 KMP 中就称为 kMP 的优化情况。如下所示：

void GetNextval(string P, int *nextval){int p_len = P.size();int i = 0; // P 的下标int j = -1; nextval[0] = -1;while (i < p_len){if (j == -1 || P[i] == P[j]){i++;j++;if (P[i] != P[j])nextval[i] = j;elsenextval[i] = nextval[j]; // 既然相同就继续往前找真前缀}elsej = nextval[j];}}

至此，关于 KMP 算法，我们就介绍到这里了。

参考

严蔚敏. 数据结构（C 语言版）阮一峰.字符串匹配的KMP算法/alps1992/article/details/47923041