子序列和子串

刷初赛题的时候被子串和子序列坑了。整理一下相关知识点。

先说一下定义，也是最基本的区别（维基百科）：

一个字符串 \(s\) 被称作另一个字符串 \(S\) 的子串，表示 \(s\) 在 \(S\) 中出现了。

一个字符串 \(s\) 被称作另一个字符串 \(S\) 的子序列，说明从序列 \(S\) 通过去除某些元素但不破坏余下元素的相对位置（在前或在后）可得到序列 \(s\) 。

比如，“中出”是“我们中出了一个叛徒”的子串（同时也是子序列）。而“XQ”是“LXTQL”的子序列，而不是子串。

一些应用：

最长回文子串/最长回文子序列：

显然，最长回文子串必须连续，而最长回文子序列可以在原字符串中不连续。
求最长回文子序列可以用递归或者动态规划等。（最近看过的NOIP2016初赛提高组阅读程序第三题就是递归求lps）
求最大回文子串还可用\(Manache\)算法等。

最长公共子串/最长公共子序列：

两者的区别是子串要求连续的，子序列不需要连续，所以在动态规划解决两种问题时，子串的状态转移方程中的表现就是，当\(s1[i]~!=~s2[j]\)时，\(dp[i][j] = 0\)。

总结一下的话，子串和子序列问题在处理上的不同是：在运算过程中，其中一位不符合要求时，子串问题将答案归零，而子序列保留之前的答案不变化。

子序列和子串

原文：https://www.cnblogs.com/miserweyte/p/11681350.html