非重叠最大得分序列的最优解

Question

在开发模拟器的过程中，我遇到了以下问题。考虑一个长度为N的字符串，以及M个子串，每个子串都有一个非负分数。特别感兴趣的是满足以下要求的子串集合：

1. 它们不重叠。
2. 它们的总得分（简单地求和）最大。
3. 它们跨越整个字符串。

我知道朴素的暴力解法的时间复杂度为O(M*N^2)。虽然这种算法的实现可能对整个项目的性能没有太大影响（远离关键路径，可以预先计算等），但我真的不太满意。

我想知道是否有更好的解决方案，如果有的话，它们是什么？指向相关代码的指针总是受欢迎的，但只有算法描述也可以。

- Michael Foukarakis

---

您在第三个要求中的意思是字符串中没有间隙（未被任何子字符串覆盖的未使用字符）吗？ - Jonathan Graehl

没错，不允许有空格。 - Michael Foukarakis

Answer 1

这可以被视为通过有向无环图找到最长路径。字符串中的每个位置都是一个节点，每个子串匹配都是一条边。你可以通过归纳法轻松证明对于最优路径上的任何节点，从开头到该节点的最优路径和从该节点到结尾的最优路径的连接等同于最优路径。由于这一点，你只需要跟踪每个节点的最优路径，并在开始考虑包含它的路径之前确保已经访问了所有以该节点结尾的边。

然后你只需要解决如何找到从一个节点开始的所有边或者在给定位置上匹配的所有子串。如果你已经知道了子串匹配的位置，那么构建哈希表就像水到渠成一样简单。如果你不知道，你仍然可以使用 Rabin-Karp 构建哈希表。

请注意，使用此方法仍需访问有向无环图中的所有边，时间复杂度为O(e)。换句话说，您必须考虑从开头到结尾连接的子字符串序列中可能出现的每个子字符串匹配一次。通过预处理子字符串以找到排除某些匹配的方法，可以获得更好的效果。我对于这种情况下是否存在一般复杂度改进存有疑虑，而任何实际改进都严重依赖于您的数据分布。

- Ants Aasma

Answer 2

O(N+M) 解法：

Set f[1..N]=-1
Set f[0]=0
for a = 0 to N-1
    if f[a] >= 0
        For each substring beginning at a
            Let b be the last index of the substring, and c its score
            If f[a]+c > f[b+1]
                Set f[b+1] = f[a]+c
                Set g[b+1] = [substring number]
Now f[N] contains the answer, or -1 if no set of substrings spans the string.
To get the substrings:
b = N
while b > 0
    Get substring number from g[N]
    Output substring number
    b = b - (length of substring)

- jcd

---

那只提供了最大分数，没有所需的非重叠子字符串集。也许我应该编辑问题，以使这一点更清晰。 - Michael Foukarakis

通过同时维护一个“以此为结尾的子串，给出当前最大值”的数组，轻松跟踪集合。 - Jonathan Graehl

对于M个子字符串，总复杂度为O(NM + M^2)。这通常比朴素解法略好，但比我链接的O(NlogN)解法差，因此我真正寻找的是一个回答“是”或“否”的问题：有没有比O(N*logN)更好的解法？ - Michael Foukarakis

我认为你误解了你链接的O(N*lg N)算法。它试图找到一个整数数组中具有最大总和的单个子序列。由于你的值都是非负的，那个算法总是会返回整个数组。 - Jonathan Graehl

哦，我明白了，你也想要子字符串。我已经修改了代码以实现这一点；它仍然是O(N+M)的。 - jcd

Answer 3

输入：

N, the number of chars in a string
e[0..N-1]: (b,c) an element of set e[a] means [a,b) is a substring with score c.  

（如果所有子字符串都是可能的，那么你可以只使用c(a,b)函数。）

例如，[1,2)表示覆盖字符串第二个字母的子字符串（半开区间）。

（空子字符串不允许；如果允许它们存在，那么只有在最多允许它们被“取”k次时才能正确处理它们）

输出：

s[i] is the score of the best substring covering of [0,i)
a[i]: [a[i],i) is the last substring used to cover [0,i); else NULL

算法 - 如果区间 e 不稀疏，则为 O(N^2)；如果 e 是允许的区间总数，则为 O(N+E)。这实际上是在无环图中找到最佳路径：

for i = 0 to N:
    a[i] <- NULL
    s[i] <- 0
a[0] <- 0
for i = 0 to N-1
    if a[i] != NULL
        for (b,c) in e[i]:
            sib <- s[i]+c
            if sib>s[b]:
                a[b] <- i
                s[b] <- sib

为了得到成本为[c]的最佳覆盖三元组[a,b,c]：

i <- N
if (a[i]==NULL):
    error "no covering"
while (a[i]!=0):
    from <- a[i]
    yield (from,i,s[i]-s[from]
    i <- from

当然，你可以将(sib,c)存储在s[b]中并节省减法操作。

- Jonathan Graehl

Answer 4

不清楚M个子字符串是作为字符序列还是输入字符串中的索引给出，但这并不会对问题造成太大影响。

假设我们有长度为N的输入字符串S和M个输入字符串Tj。令Lj为Tj的长度，Pj为字符串Sj的得分。我们称该字符串为

这被称为动态规划或DP。您需要保持一个长度为N的int数组res，其中第i个元素表示如果只有从第i个元素开始的子字符串，则可以获得的最高分数（例如，如果输入为“abcd”，则res[2]将表示您可以获得的“cd”的最佳分数）。

然后，您需要从末尾到开头迭代此数组，并检查是否可以从第i个字符开始字符串Sj。如果可以，则(res[i + Lj] + Pj)的结果显然是可实现的。遍历所有Sj，对于所有可以应用于第i个字符的Sj，res[i] = max(res[i + Lj] + Pj)。

res[0]将是您的最终答案。

- Olexiy

---

你应该预先计算出哪些字符串可以应用于哪些位置，以摆脱 N^2 并使你的算法达到 O(N*M)（你应该使用一些更快的字符串搜索算法）。 - Olexiy

我不明白你从哪里得到了N^2。算法是NM - 你检查每个M字符串在每个N位置上。你能解释一下为什么你认为它是N^2M吗？ - Olexiy