如何找到一个字符串的不同子序列数？

  • Z时代
  • 2024-01-10
  • 分类：问答

这是另一个spoj问题，询问如何找到字符串的不同子序列数？

例如，

AAA

ABCDEFG

编解码器

4

128

496

我怎么解决这个问题 ？

回答：

这是一个经典的动态编程问题。

让：

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 - 1]我使用过的任何地方a[i]。另外，mod如果要提交代码，请记住将计算包装在函数中。应该这样实现：

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

为了正确处理某些语言（例如C / C ++）中的负值。

以上是 如何找到一个字符串的不同子序列数？ 的全部内容， 来源链接： utcz.com/qa/419055.html

回到顶部