string - 如何找到字符串的不同子序列的数量？

Question

这是另一个 spoj problem询问如何查找字符串的不同子序列的数量？

例如，

Input
AAA
ABCDEFG
CODECRAFT

Output
4
128
496

我该如何解决这个问题？

Answer 1

这是一个经典的动态规划问题。

让:

dp[i] = number of distinct subsequences ending with a[i]
sum[i] = dp[1] + dp[2] + ... + dp[i]. So sum[n] will be your answer.
last[i] = last position of character i in the given string.

空字符串有一个子序列，所以 dp[0] = 1。

read a
n = strlen(a)
for i = 1 to n
  dp[i] = sum[i - 1] - sum[last[a[i]] - 1]
  sum[i] = sum[i - 1] + dp[i]
  last[a[i]] = i

return sum[n]

解释

dp[i] = sum[i - 1] - sum[last[a[i]] - 1]

最初，我们假设我们可以将 a[i] 附加到所有以前面的字符结尾的子序列，但这可能违反了计数子序列需要不同的条件。请记住，last[a[i]] 为我们提供了直到现在 a[i] 出现的最后位置。我们多计的唯一子序列是那些附加到前面的 a[i] 的子序列，所以我们减去那些。

sum[i] = sum[i - 1] + dp[i]
last[a[i]] = i

根据定义更新这些值。

如果您的索引从 0 开始，请在我使用 a[i] 的地方使用 a[i - 1]。如果您要提交代码，还请记住将您的计算包装在 mod 函数中。这应该像这样实现:

mod(x) = (x % m + m) % m

为了在某些语言(如C/C++)中正确处理负值。