最长公共子序列的变种：带限制的最长公共子序列（限制子序列必须包含某个特定子串）

题目描述：
给定两个字符串s1和s2，以及一个限制字符串t。要求找出s1和s2的最长公共子序列，且这个公共子序列必须包含t作为其子串（即t必须是这个公共子序列的连续部分）。

示例：
s1 = "abcde", s2 = "ace", t = "c"
最长公共子序列是 "ace"，其中"c"是连续部分，满足条件

解题思路：
这个问题可以分解为三个部分的组合：t之前的部分、t本身、t之后的部分。

详细解题步骤：

1. 预处理阶段：
   我们需要计算四个二维DP表：

• dp_pre[i][j]: s1前i个字符和s2前j个字符的LCS长度
• dp_suf[i][j]: s1从第i个字符开始到结尾，和s2从第j个字符开始到结尾的LCS长度
• match_pre[i][j]: 在s1前i个字符和s2前j个字符中，t能够匹配完成的最大前缀长度
• match_suf[i][j]: 在s1从第i个字符开始到结尾，和s2从第j个字符开始到结尾中，t能够匹配完成的最大后缀长度

2. 主要算法步骤：
   步骤1：计算标准的LCS预处理表

# dp_pre[i][j] = s1[0:i]和s2[0:j]的LCS长度
for i in range(1, len(s1)+1):
    for j in range(1, len(s2)+1):
        if s1[i-1] == s2[j-1]:
            dp_pre[i][j] = dp_pre[i-1][j-1] + 1
        else:
            dp_pre[i][j] = max(dp_pre[i-1][j], dp_pre[i][j-1])

步骤2：计算反向的LCS表（从后往前）

# dp_suf[i][j] = s1[i:]和s2[j:]的LCS长度
for i in range(len(s1)-1, -1, -1):
    for j in range(len(s2)-1, -1, -1):
        if s1[i] == s2[j]:
            dp_suf[i][j] = dp_suf[i+1][j+1] + 1
        else:
            dp_suf[i][j] = max(dp_suf[i+1][j], dp_suf[i][j+1])

步骤3：计算t在s1和s2中的匹配情况
我们需要找到所有位置(i,j)，使得从s1的i位置和s2的j位置开始，能够完整匹配t

步骤4：组合结果
对于每个可能匹配t的位置对(i,j)，其中t在s1中从i开始匹配，在s2中从j开始匹配：
结果 = dp_pre[i][j] + len(t) + dp_suf[i+len(t)][j+len(t)]

3. 边界情况处理：

• 如果t为空字符串，问题退化为标准LCS
• 如果t比s1或s2长，直接返回0
• 如果t根本不在s1和s2的公共子序列中出现，返回0

4. 时间复杂度分析：
   预处理阶段：O(n×m)，其中n和m分别是s1和s2的长度
   匹配阶段：O(k×n×m)，其中k是t的长度
   总时间复杂度：O(n×m×k)

这个算法的关键在于将复杂问题分解为几个标准的子问题，然后通过组合这些子问题的解来得到最终答案。