共计 4576 个字符，预计需要花费 12 分钟才能阅读完成。
一、最长公共子序列 LCS (Longest Common Subsequence)
1. 题目
给定两个串序列 A、B，找出两个串的最长公共子序列 LCS 包含的元素和长度。
注意：
(1) 一个序列 S 任意删除若干个字符得到新序列 T，则 T 叫做 S 的子序列。
(2) 与最长公共子串 (Longest Common Substring) 相区别，最长公共子串要求元素相同且连续，而最长公共子序列只要求元素出现的顺序一致，并不要求连续。即对于
串 A：abcde
串 B：bcdae
最长公共子串为：bcd
最长公共子序列为：bcde
- 奇妙的算法之 LCS 妙解
2. 分析
该算法主要使用了动态规划算法(DP)。
(1). LCS 解题的记号
(2). 第一种情况 xm = yn
(3). 第二种情况 xm != yn
(4). 数据结构
算法中使用到的数据结构如下：
(5). 例子
示例：
X = < A，B，C，B，D，A，B >
Y = < B，D，C，A，B，A >
最长公共子序列为：<B，C，B，A>
该过程生成的二维数组如下图所示：
(6). 进一步思考
3. 代码
int m = 7 + 1, n = 6 + 1;
int c[m][n], b[m][n];
// 注意 A、B 字符串的第一个字符是不进行计算的，可以用_来进行占位
char A[] = "_ABCBDAB";
char B[] = "_BDCABA";
// 对第 0 行和第 0 列进行初始化
// c 中 0 为初始值，1 代表左，2 代表上，3 代表左上
for (int i = 0; i < m; i++)
b[i][0] = c[i][0] = 0;
for (int j = 0; j < n; j++)
b[0][j] = c[0][j] = 0;
for (int i = 1; i < m; i++){for (int j = 1; j < n; j++){if (A[i] == B[j]){c[i][j] = c[i - 1][j - 1] + 1;
b[i][j] = 3;
} else{if (c[i - 1][j] >= c[i][j - 1]){c[i][j] = c[i - 1][j];
b[i][j] = 2;
} else{c[i][j] = c[i][j - 1];
b[i][j] = 1;
}
}
}
}
// 输出二维数组的值
for (int i = 0; i < m; i++){for (int j = 0; j < n; j++){cout << c[i][j] << "(";
switch (b[i][j]){
case 1: cout << "←"; break;
case 2: cout << "↑"; break;
case 3: cout << "↖"; break;
default: cout << " "; break;
}
cout << ")";
}
cout << endl;
}4. 推广
LCS 的应用：最长递增子序列 LIS（Longest Increasing Subsequence）
给定一个长度为 N 的数组，找出一个最长的单调递增子序列。
例如：给定数组{5，6，7，1，2，8}，则其最长的单调递增子序列为{5，6，7，8}，长度为 4。
分析：其实此 LIS 问题可以转换成最长公子序列问题，为什么呢？
原数组为 A {5，6，7，1，2，8}
排序后：A’{1，2，5，6，7，8}
因为，原数组 A 的子序列顺序保持不变，而且排序后 A’本身就是递增的，这样，就保证了两序列的最
长公共子序列的递增特性。如此，若想求数组 A 的最长递增子序列，其实就是求数组 A 与它的排序数
组 A’的最长公共子序列。
（此外，本题也可以直接使用动态规划 / 贪心法来求解）
5. 应用
求两个序列中最长的公共子序列算法，广泛的应用在图形相似处理、媒体流的相似比较、计算生物学
方面。生物学家常常利用该算法进行基因序列比对，由此推测序列的结构、功能和演化过程。
LCS 可以描述两段文字之间的“相似度”，即它们的雷同程度，从而能够用来辨别抄袭。另一方面，对
一段文字进行修改之后，计算改动前后文字的最长公共子序列，将除此子序列外的部分提取出来，这
种方法判断修改的部分，往往十分准确。简而言之，百度知道、百度百科都用得上。
二、最长递增子序列 LIS (Longest Increasing Subsequence)
1. 题目
给定一个串，找出该串的最长递增子序列 LIS 包含的元素和长度。
最长递增子序列，基本定义与最长公共子序列相似，还要求该序列是递增序列。
2. 分析
注意：在计算
b[i]的时候，需要遍历b数组在i之前所有位置 j 的值，取b[j]为最大值且aj<ai，此时b[i] = b[j] + 1
3. 代码
// a 数组存储序列元素
// b 数组存储 LIS 序列长度
// c 数组存储 b[i]的计算来源位置的下标
int a[] = { 1, 4, 6, 2, 8, 9, 7};
int n = 7;
int b[n], c[n];
int i, j, k;
// 初始化
for (int i = 0; i < n; i++) {b[i] = 1;
c[i] = -1;
}
for (i = 1; i < n; i++) {
k = -1;
for (j = i - 1; j >= 0; j--) {if (a[j] < a[i] && b[j] > k) {b[i] = b[j] + 1;
c[i] = j;
k = b[j];
}
}
}
// 自定义输出数组函数，print(int a[], int n)
cout << "array:";
print(a, n);
cout << "LIS:";
print(b, n);
cout << "pos:";
print(c, n);
// stack 用于存储序列元素
// max 为最大的 LIS 序列的长度
int stack[n];
int top = -1, max = -1;
k = -1;
for (i = 0; i < n; i++)
if (max < b[i]) {max = b[i];
k = i;
}
cout << "max:" << max << endl;
while (c[k] != -1) {stack[++top] = a[k];
k = c[k];
}
stack[++top] = a[k];
cout << "LIS 序列:";
while (top != -1) {cout << stack[top--] << ",";
}4. 输出
array: 1, 4, 6, 2, 8, 9, 7
LIS: 1, 2, 3, 2, 4, 5, 4
pos: -1, 0, 1, 0, 2, 4, 2
max: 5
LIS 序列: 1, 4, 6, 8, 9三、KMP 算法 (The Knuth-Morris-Pratt Algorithm)
1. 题目
在计算机科学中，Knuth-Morris-Pratt 字符串查找算法（简称为 KMP 算法）可在一个主文本字符串 S 内查找一个词 W 的出现位置。此算法通过运用对这个词在不匹配时本身就包含足够的信息来确定下一个匹配将在哪里开始的发现，从而避免重新检查先前匹配的字符。
KMP 算法解决的是字符串的查找问题，即：
给定文本串 text 和模式串 pattern，从文本串 text 中找出模式串 pattern 第一次出现的位置。
- 从头到尾彻底理解 KMP（2014 年 8 月 22 日版）– 结构之法 算法之道 – CSDN 博客
- 字符串匹配：KMP 算法 by Liam Huang
- Knuth-Morris-Pratt algorithm (description and C code by Christian Charras and Thierry Lecroq)
2. 分析
(1). 暴力求解 (Brute Force)
(2). 改进 BF，使其成为 KMP
(3). KMP 算法
算法步骤：
- 1. 先求模式串的 next 数组
- 2. 进行模式串和目标串的匹配
(4). 优化 next 数组，加快 KMP 匹配速度
(5). KMP 算法性能分析
(6). 扩展
3. 代码
(1). 暴力求解
/**
* 暴力法解字符串匹配问题
*/
int brute_force_search(const char* s, const char* p){
// i 为当前匹配到的原始串首位
// j 为模式串的匹配位置
int i=0, j=0;
int size = strlen(p);
int last = strlen(s) - size;
while (i<=last && j<size){if(s[i+j] == p[j])
j++;
else{
i++;
j=0;
}
}
if(j>=size) return i;
return -1;
}(2). 常规 KMP
/**
* 得到 next 数组
*/
void get_next(char* p, int next[]){int len = strlen(p);
next[0] = -1;
int k = next[0];
int j = 0;
while (j < len - 1){// 此时, k 即 next[j-1]，且 p[k]表示前缀，p[j]表示后缀
// 注：k==- 1 表示未找到 k 前缀与 k 后缀相等，首次分析可忽略
if(k == -1 || p[j] == p[k]){
++j;
++k;
next[j] = k;
} else {// p[j]与 p[k]失配，则继续递归计算前缀 p[next[k]]
k = next[k];
}
}
}
int kmp(char s[], char p[], int next[]){int s_len = strlen(s);
int p_len = strlen(p);
int i = 0, j = -1;
while (i<s_len && j<p_len){if(j==-1 || s[i] == p[j]){
++i;
++j;
} else {j = next[j];
}
}
if (j >= p_len)
return i - p_len;
return -1;
}(3). 变种 KMP
/**
* 得到优化之后的 next 数组，滑动匹配距离更大了，便于滑动匹配
*/
void get_next_2(char* p, int next[]){int len = strlen(p);
next[0] = -1;
int k = next[0];
int j = 0;
while (j < len - 1){// 此时, k 即 next[j-1]，且 p[k]表示前缀，p[j]表示后缀
// 注：k==- 1 表示未找到 k 前缀与 k 后缀相等，首次分析可忽略
if(k == -1 || p[j] == p[k]){
++j;
++k;
if(p[j] == p[k])
next[j] = next[k];
else
next[j] = k;
} else {// p[j]与 p[k]失配，则继续递归计算前缀 p[next[k]]
k = next[k];
}
}
}
int kmp(char s[], char p[], int next[]){int s_len = strlen(s);
int p_len = strlen(p);
int i = 0, j = -1;
while (i<s_len && j<p_len){if(j==-1 || s[i] == p[j]){
++i;
++j;
} else {j = next[j];
}
}
if (j >= p_len)
return i - p_len;
return -1;
}四、PowerString 问题 (KMP 算法的应用)
1. 题目
给定一个长度为 n 的字符串 S，如果存在一个字符串 T，重复若干次 T 能够得到 S，那么，S 叫做周期串，T 叫做 S 的一个周期。
如：字符串 abababab 是周期串，abab、ab 都是它的周期，其中，ab 是它的最小周期。
设计一个算法，计算 S 的最小周期。如果 S 不存在周期，返回空串。
2. 分析
3. 代码
int power_string(char* p){int len = strlen(p);
if(!len) return -1;
int next[len];
int k = next[0] = -1;
int j = 0;
while (j < len - 1){if(k == -1 || p[j+1] == p[k]){
++j;
++k;
next[j] = k;
} else {k = next[k];
}
}
int last = next[len-1];
if(last == 0) return -1;
if(len % (len - last) == 0) return len - last;
return -1;
}
