具有N个子串限制的递归最长公共子序列

问题描述

我真的被困在一个问题上了，我得到了一个字符串输入S，另一个代表整个子串的字符串输入U和一个非负的整数m。方法是LCS(S，U，m)。

例如：设S=aabacaab"；，U=aab"；，m=2，则有下列子字符串组合：

[a][ab]acaab

[a]abaca[ab]

a[a]baca[ab]

aab[a]ca[ab]

aabac[a][ab]

[aa][b]acaab

[aa]bacaa[b]

aabac[aa][b]

SOlcs(S, U, m)返回8，因为我们有8个不同的U子字符串组合，限制为m子字符串数量。

我最初的想法是将S的第一个字符与U的第一个字符进行比较，并通过将S和U都缩写来递归向下。但是，由于m的原因，我无法确定m应该如何减少，因为缩写的S和U与以前的状态没有任何引用。

---

解决方案

在处理字符串的动态编程时，我的子问题应该是什么的答案通常是前缀、后缀或子字符串。

从您的最后说明中，您已经正确地认识到，我们可以通过解决后缀问题来解决原始问题。我们还知道，我们的子问题必须知道我们还剩下多少块可以使用。此时，我们可以猜测子问题是什么，并尝试定义一个公式。

我们可以将f(i,j,k)设为使用S的最后i字母精确匹配k子字符串的j字母的方法数。边缘情况是什么？如果j和k都为0，则我们没有什么可做的；只有一种方法可以什么都不做。如果i<j我们无法匹配j字母，如果j<k我们无法将j字母拆分成足够多的片段。

最后，您必须定义主递归。首先，我们可以跳过S这个字母，它将f(i-1,j,k)作为总和。现在，让Match-Length(i,j)是S[-i:]开始匹配U[-j:]的连续位数。我们需要添加所有可能的匹配：对于每个长度l，1 <= l <= Match-Length(i,j)，我们必须添加f(i-l, j-l, k-1)。这涵盖了所有案例。

编辑：用户qouify发布了一个更好的解决方案。这个DP公式的直接平移在时间O(|S| |U|^2 m)上运行，而他们的公式在O(|S| |U| m)上运行。我的公式可以修改以匹配运行时，但您需要计算前缀和，以便在经过预处理和记忆后的O(1)时间内可以找到f(i-l, j-l, k-1)的每个和。