最长公共子序列的变种：带字符限制的最长公共子序列（进阶版：限制某些字符必须连续出现） 题目描述： 给定两个字符串s和t，以及一个模式串pattern。要求找出s和t的最长公共子序列，且该子序列必须包含pattern作为连续子串。也就是说，找到的公共子序列需要包含完整的、连续的pattern字符序列。 解题过程： 问题理解： 我们需要找到s和t的一个公共子序列，这个子序列需要满足两个条件： 是s和t的公共子序列 包含完整的pattern作为连续子串 状态定义： 定义三维DP数组：dp[ i][ j][ k ] i: 在s中考虑到第i个字符（1-based indexing） j: 在t中考虑到第j个字符 k: 表示当前匹配pattern的状态（0 ≤ k ≤ len(pattern)） k的含义： k = 0：还没有开始匹配pattern 1 ≤ k ≤ len(pattern)：已经匹配了pattern的前k个字符 k = len(pattern)：已经完整匹配了pattern 状态转移： 我们需要考虑四种状态转移情况： 情况1：不选择s[ i]和t[ j ] dp[ i][ j][ k] = max(dp[ i][ j][ k], dp[ i-1][ j-1][ k ]) 情况2：选择s[ i]和t[ j]，且s[ i] = t[ j ] 此时需要根据当前匹配状态k来更新： 如果k = 0：还没有开始匹配pattern 如果s[ i] = pattern[ 0]：可以开始匹配，dp[ i][ j][ 1] = max(dp[ i][ j][ 1], dp[ i-1][ j-1][ 0 ] + 1) 否则：继续保持在状态0，dp[ i][ j][ 0] = max(dp[ i][ j][ 0], dp[ i-1][ j-1][ 0 ] + 1) 如果1 ≤ k < len(pattern)：正在匹配pattern中 如果s[ i] = pattern[ k]：继续匹配下一个字符，dp[ i][ j][ k+1] = max(dp[ i][ j][ k+1], dp[ i-1][ j-1][ k ] + 1) 否则：匹配失败，但可以选择这个字符，dp[ i][ j][ k] = max(dp[ i][ j][ k], dp[ i-1][ j-1][ k ] + 1) 如果k = len(pattern)：已经完成pattern匹配 可以选择任意字符，dp[ i][ j][ k] = max(dp[ i][ j][ k], dp[ i-1][ j-1][ k ] + 1) 情况3：只选择s[ i]，不选择t[ j ] dp[ i][ j][ k] = max(dp[ i][ j][ k], dp[ i-1][ j][ k ]) 情况4：只选择t[ j]，不选择s[ i ] dp[ i][ j][ k] = max(dp[ i][ j][ k], dp[ i][ j-1][ k ]) 初始化： dp[ 0][ j][ 0 ] = 0（s为空字符串） dp[ i][ 0][ 0 ] = 0（t为空字符串） 其他状态初始化为负无穷（表示不可达状态） 最终答案： 我们需要找到包含完整pattern的公共子序列，所以答案是max(dp[ len(s)][ len(t)][ len(pattern) ], 0)。如果结果为负，说明不存在满足条件的公共子序列。 复杂度分析： 时间复杂度：O(n×m×l)，其中n是s的长度，m是t的长度，l是pattern的长度 空间复杂度：O(n×m×l)，可以通过滚动数组优化到O(m×l) 这个算法通过三维DP状态精确跟踪了pattern的匹配进度，确保最终找到的公共子序列一定包含完整的pattern作为连续子串。