线性动态规划：最长公共子序列的变种——带限制的最长公共子序列
字数 1714 2025-10-28 22:11:24

线性动态规划：最长公共子序列的变种——带限制的最长公共子序列

题目描述
给定两个字符串 s1 和 s2，以及一个字符串 evil，要求找出 s1 和 s2 的最长公共子序列（LCS），且该子序列中不包含 evil 作为连续子串。返回满足条件的最长公共子序列的长度。如果不存在这样的子序列，返回 0。

示例
输入：
s1 = "abcde", s2 = "ace", evil = "c"
输出：2
解释：s1 和 s2 的 LCS 是 "ace"，但 "ace" 包含子串 "c"，因此不合法。合法的 LCS 是 "ae" 或 "ce"，长度为 2。

解题过程

步骤1：理解问题与常规LCS的区别
常规 LCS 使用动态规划，定义 dp[i][j] 表示 s1[0..i-1] 和 s2[0..j-1] 的 LCS 长度。本题增加限制：LCS 不能包含 evil 子串。这意味着我们需要在状态中跟踪当前已匹配的 evil 前缀长度，避免匹配到完整的 evil。

步骤2：状态设计
定义 dp[i][j][k]：

  • i：考虑 s1 的前 i 个字符（0 ≤ i ≤ len(s1)）
  • j：考虑 s2 的前 j 个字符（0 ≤ j ≤ len(s2)）
  • k：当前公共子序列的后缀与 evil 的最长匹配前缀长度（0 ≤ k < len(evil)）
    状态值：在满足不出现完整 evil 的条件下，当前的最长公共子序列长度。

注意：k 不能等于 len(evil)，因为那样意味着已出现 evil 子串，非法状态。

步骤3：状态转移
我们需要考虑两种情况：

  1. 不选当前字符：继承之前的状态
    • 跳过 s1[i-1]：dp[i][j][k] = max(dp[i][j][k], dp[i-1][j][k])
    • 跳过 s2[j-1]：dp[i][j][k] = max(dp[i][j][k], dp[i][j-1][k])
  2. 选当前字符（仅当 s1[i-1] == s2[j-1] 时）：
    • 设当前字符为 c = s1[i-1]。
    • 我们需要计算加入 c 后，evil 的匹配前缀长度如何变化。这可以通过 KMP 的失配函数（next数组）预处理。

预处理next数组：
对 evil 计算前缀函数 next[m]，其中 next[t] 表示 evil[0..t-1] 的最长公共真前后缀长度。
定义函数 getNextState(k, c)：从当前匹配长度 k 开始，加入字符 c 后，新的匹配长度。

  • 如果 evil[k] == c，则新匹配长度 = k+1
  • 否则，回溯到 next[k] 继续匹配，直到匹配或为0。

状态转移方程（选字符）：
如果 s1[i-1] == s2[j-1]，设 c = s1[i-1]，计算 nk = getNextState(k, c)。
如果 nk < len(evil)（未形成完整evil），则：
dp[i][j][nk] = max(dp[i][j][nk], dp[i-1][j-1][k] + 1)

步骤4：初始化
dp[0][j][0] = 0，dp[i][0][0] = 0：空字符串与任何字符串的LCS为0，且匹配长度为0。
其他状态初始化为负无穷（表示不可达）。

步骤5：答案提取
答案是所有 dp[len(s1)][len(s2)][k]（0 ≤ k < len(evil)）的最大值。

步骤6：复杂度分析

  • 时间复杂度：O(n * m * L)，其中 n = len(s1), m = len(s2), L = len(evil)
  • 空间复杂度：可优化到 O(m * L)

总结
本题通过将 evil 的匹配状态融入DP，结合KMP的失配处理，有效避免了非法子串的出现。关键在于理解状态 k 表示当前已匹配的 evil 前缀长度，并在加入字符时更新该状态。

线性动态规划：最长公共子序列的变种——带限制的最长公共子序列 题目描述 给定两个字符串 s1 和 s2 ，以及一个字符串 evil ，要求找出 s1 和 s2 的最长公共子序列（LCS），且该子序列中 不包含 evil 作为连续子串。返回满足条件的最长公共子序列的长度。如果不存在这样的子序列，返回 0。 示例 输入： s1 = "abcde", s2 = "ace", evil = "c" 输出：2 解释：s1 和 s2 的 LCS 是 "ace"，但 "ace" 包含子串 "c"，因此不合法。合法的 LCS 是 "ae" 或 "ce"，长度为 2。 解题过程 步骤1：理解问题与常规LCS的区别 常规 LCS 使用动态规划，定义 dp[i][j] 表示 s1[0..i-1] 和 s2[0..j-1] 的 LCS 长度。本题增加限制：LCS 不能包含 evil 子串。这意味着我们需要在状态中跟踪当前已匹配的 evil 前缀长度，避免匹配到完整的 evil 。 步骤2：状态设计 定义 dp[i][j][k] ： i ：考虑 s1 的前 i 个字符（0 ≤ i ≤ len(s1)） j ：考虑 s2 的前 j 个字符（0 ≤ j ≤ len(s2)） k ：当前公共子序列的后缀与 evil 的最长匹配前缀长度（0 ≤ k < len(evil)） 状态值：在满足不出现完整 evil 的条件下，当前的最长公共子序列长度。 注意 ： k 不能等于 len(evil) ，因为那样意味着已出现 evil 子串，非法状态。 步骤3：状态转移 我们需要考虑两种情况： 不选当前字符 ：继承之前的状态 跳过 s1[i-1] ： dp[i][j][k] = max(dp[i][j][k], dp[i-1][j][k]) 跳过 s2[j-1] ： dp[i][j][k] = max(dp[i][j][k], dp[i][j-1][k]) 选当前字符 （仅当 s1[i-1] == s2[j-1] 时）： 设当前字符为 c = s1[i-1] 。 我们需要计算加入 c 后， evil 的匹配前缀长度如何变化。这可以通过 KMP 的失配函数（next数组）预处理。 预处理next数组 ： 对 evil 计算前缀函数 next[m] ，其中 next[t] 表示 evil[0..t-1] 的最长公共真前后缀长度。 定义函数 getNextState(k, c) ：从当前匹配长度 k 开始，加入字符 c 后，新的匹配长度。 如果 evil[k] == c ，则新匹配长度 = k+1 否则，回溯到 next[k] 继续匹配，直到匹配或为0。 状态转移方程（选字符） ： 如果 s1[i-1] == s2[j-1] ，设 c = s1[i-1] ，计算 nk = getNextState(k, c) 。 如果 nk < len(evil) （未形成完整evil），则： dp[i][j][nk] = max(dp[i][j][nk], dp[i-1][j-1][k] + 1) 步骤4：初始化 dp[0][j][0] = 0 ， dp[i][0][0] = 0 ：空字符串与任何字符串的LCS为0，且匹配长度为0。 其他状态初始化为负无穷（表示不可达）。 步骤5：答案提取 答案是所有 dp[len(s1)][len(s2)][k] （0 ≤ k < len(evil)）的最大值。 步骤6：复杂度分析 时间复杂度：O(n * m * L)，其中 n = len(s1), m = len(s2), L = len(evil) 空间复杂度：可优化到 O(m * L) 总结 本题通过将 evil 的匹配状态融入DP，结合KMP的失配处理，有效避免了非法子串的出现。关键在于理解状态 k 表示当前已匹配的 evil 前缀长度，并在加入字符时更新该状态。