如何查找字符串的不同子序列的数量？

Question

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

例如,

输入
AAA
ABCDEFG
CODECRAFT

输出
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 - 1]在我使用的任何地方使用a[i].mod如果您要提交代码,请记住将计算包装在函数中.这应该像这样实现:

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

为了正确处理某些语言中的负值(例如C/C++).

Answer 2

这个问题有一个更容易的解决方案.

这个想法是:如果字符串的所有字符都是不同的,则子序列的总数是 2^n.Now,如果我们找到之前已经发生的任何字符,我们应该只考虑它的最后一次出现(否则序列将不会是不同的).所以我们必须减去由于之前发生的子序列的数量.

我的实现是这样的:

read s
dp[0] = 1
len = strlen(s)
last[s.length()] = {-1} //declaring `last` array with same as length of string `s` and all elements initialized with -1.

for (i = 1; i <= len; i++) 
{
    dp[i] = (dp[i - 1] * 2)
    if (last[s[i]] > 0) dp[i] = (dp[i] - dp[last[s[i]] - 1])
    last[s[i]] = i
}