上周，我们讲到了字符串中的字符串哈希、字典树 Trie。不知道大家小本本记好知识点了没？如果还没学会的，或者还没学的小伙伴们，记得看这篇文章哈~
本周，我们将讲字符串中的 Manacher 回文算法、KMP 字符串匹配。
Manacher 回文算法
所谓回文字串，即正着读和倒着读结果都一样的字符串，比如:a, aba, abccba 都是回文串, ab, abb, abca 都不是回文串。
暴力求解的思路：找到字符串的所有子串，遍历每一个子串以验证它们是否为回文串。一个子串由子串的起点和终点确定，因此对于一个长度为 n 的字符串，共有 n^2 个子串。
这些子串的平均长度大约是 n/2，因此这个解法的时间复杂度是 O(n^3)。
我们能不能提高效率呢？当然可以！这里给大家介绍 manacher 算法。
它是一个能够在线性时间内得到一个字符串中最长回文子串的算法，性能比其他的算法（如哈希）还要优秀，且不会被造数据卡住，是处理回文串最有效的工具。
参考代码如下：
def manacher(s):# 预处理s = '#'+'#'.join(s)+'#'RL = [0]*len(s)MaxRight = 0pos = 0MaxLen = 0for i in range(len(s)):if i < MaxRight:= min(RL[2*pos-i], MaxRight-i)else:= 1# 尝试扩展，注意处理边界while i-RL[i] >= 0 and i+RL[i] < len(s) and s[i-RL[i]] == s[i+RL[i]]:+= 1# 更新MaxRight,posif RL[i]+i-1 > MaxRight:MaxRight = RL[i]+i-1pos = i# 更新最长回文串的长度MaxLen = max(MaxLen, RL[i])return MaxLen-1
练习题→https://www.lanqiao.cn/problems/1225/learning/
KMP 字符串匹配
字符串匹配是极为常见的一种模式匹配。简单地说，就是判断主串 T 中是否出现模式串 P，即 P 为 T 的子串。特别地，定义主串 T[0...n-1], 模式串为 P [0...p-1], 则主串与模式串的长度各为 n 与 p。
暴力匹配方法的思想非常朴素：
-
依次从主串的首字符开始，与模式串逐一进行匹配；
-
遇到失配时，则移到主串的第二个字符，将其与模式串首字符比较，逐一进行匹配；
-
重复上述步骤，直至能匹配上，或剩下主串的长度不足以进行匹配。
参考代码如下：
def brute_force_match(t, p):tlen = len(t)plen = len(p)for i in range(tlen):j = 0while t[i+j] == p[j] and j < plen:j = j+1if j == plen:return ireturn -1
KMP 算法思想归纳如下：将主串 T 的第一个字符与模式串 P 的第一个字符进行匹配。
如果相等，则依次比较 T 和 P 的下一个字符。如果不相等，则主串 T 移动(已匹配字符数-对应的部分匹配值)位，继续匹配。
练习题→https://www.lanqiao.cn/problems/1203/learning/
字符串的知识点就告一段落了，我们将开启新的征程——动态规划。
它是运筹学的一个分支，是求解决策过程最优化的过程。
一般来说，动态规划求解主要包括以下步骤：
-
划分阶段
把问题划分成子问题，类似于分治法，每个阶段一般是有序的。
-
定义状态
每个阶段，都有属于自己的最优状态，每一个阶段的最优状态，可以从前面阶段的最优状态中转化获得。
-
状态转化
不同阶段之间的转化关系，就是状态转移方程，定义好它们之间的递推关系，就是极其重要的一步。
-
逆向求解
一般来说我们要求解一个状态，需要先把前面的状态先求解。那么逆向就是自底向上，也就是先挨个把前面的状态求解，再使用前面的状态求解后面的状态。（注意最初的状态定义必须准确，边界值需要处理好）
经典线性DP
首先，我们讲的是经典线性 DP。
1.最长上升子序列（LIS）
它在计算机科学上是指一个序列中最长的单调递增的子序列。
有两种，时间复杂度分别为 O(n^2) 与 O(n log n)，空间复杂度均为 O(n)。
1）O(n^2)
using namespace std;stack<int> index;int a[15010], dp[15010], front[15010];//front记结点前驱int n;inline void ir() {cin >> n;return;}int main() {ir();int maxn = 0;for (int i = 1; i <= n; i++){scanf_s("%d", &a[i]);dp[i] = 1;front[i] = -1; //初始化for (int j = 1; j < i; j++)if (a[j] < a[i]){if (dp[j] + 1 > dp[i]){dp[i] = dp[j] + 1;front[i] = j;}}maxn = max(maxn, dp[i]);}cout << maxn << endl;int k = 0;for (int i = 1; i <= n; i++)if (dp[i] == maxn)k = i;while (k != -1){index.push(k);k = front[k];}while (!index.empty()) {cout << a[index.top()] << endl;index.pop();}return 0;}
2）O(n log n)
using namespace std;int n,a[20010];int c[20010];int len=0;int find(int x){int l=1,r=len,mid;while(l<=r){mid=(l+r)>>1;if(x>c[mid])l=mid+1;//记忆方法:求上升序列，就表示x更大，那么就是大于elser=mid-1;}return l;}int main(){scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",&a[i]);for(int i=1;i<=n;i++){int k=find(a[i]);c[k]=a[i];len=max(len,k);}printf("%d",len);return 0;}
LIS 经常用于确定一个代价最小的调整方案，使一个序列变为升序。只需要固定 LIS 中的元素，调整其他元素即可。
练习题→https://www.lanqiao.cn/problems/1188/learning/
2）最长公共子序列（LCS）
一个序列，如果是两个或多个已知序列的子序列，且是所有子序列中最长的，则为最长公共子序列。
举个例子：
str1 = “abdbcabd"str2 = "abbcdd"两者最长的公共子序列为 ”abbcd“，长度为 5。
如何求解两个字符串的最长公共子序列呢？
我们可以知道这个问题可以分解为更小的问题，思考一下，比如长度为 n 的字符串 str1 和长度为 m 的字符串 str2，两者的最长公共子序列，是不是可以从 str1 前长度为 n-1 的子串与 str2 前长度为 m-1 的子串的最长公共子序列中得知呢？
答案是肯定的。
实现代码如下：
public class LCS {public static void main(String[] args) {findLCS("abbcdd", "abdbcabd");}public static int findLCS(String str1, String str2) {int n = str1.length();int m = str2.length();// 状态定义int[][] dp = new int[n + 1][m + 1];// 初始化状态for (int i = 0; i <= n; i++) {for (int j = 0; j <= m; j++) {dp[i][j] = 0;}}for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {// 如果两个字符相等if (str1.charAt(i - 1) == str2.charAt(j - 1)) {dp[i][j] = dp[i - 1][j - 1] + 1;} else {// 不相等的时候，取 dp[i - 1][j] 和 dp[i][j - 1] 的最大dp[i][j] = dp[i - 1][j] > dp[i][j - 1] ? dp[i - 1][j] : dp[i][j - 1];}}}print(dp);return dp[n][m];}// 打印矩阵public static void print(int[][] results) {for (int i = 0; i < results.length; i++) {for (int j = 0; j < results[0].length; j++) {System.out.print(results[i][j] + " ");}System.out.println("");}System.out.println("最长公共子串的长度为： " +results[results.length - 1][results[0].length - 1]);}}
练习题→https://www.lanqiao.cn/problems/1189/learning/
结合 LIS 和 LCS，我们可以刷以下题目;
https://www.lanqiao.cn/problems/1190/learning/
本周的【算法学与练】就到此结束了，如果你想进行刷题，欢迎加入专属算法刷题群~我们下周见~
▼立即加入算法刷题群▼
原文始发于微信公众号（蓝桥云课精选）：如何系统地学习算法？这一篇告诉你！
- 左青龙
- 微信扫一扫
-
- 右白虎
- 微信扫一扫
-
评论