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

本文介绍了如何找到一个字符串的不同子序列数？的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述 这是另一个 spoj问题，它询问如何查找字符串的不同子序列数？Here is another spoj problem that asks how to find the number of distinct subsequences of a string ?例如， 输出 4 128 496 Output 4 128 496 我该如何解决这个问题？How can I solve this problem ?推荐答案这是一个经典的动态编程问题。It's a classic dynamic programming problem.让：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 。A null string has one subsequence, so dp[0] = 1.read an = 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]] = ireturn sum[n] 说明 dp[i] = sum[i - 1] - sum[last[a[i]] - 1]最初，我们假定可以附加 a [i] 到所有以先前字符结尾的子序列，但这可能违反了计数子序列必须是不同的条件。请记住， last [a [i]] 给了我们最近出现的最后位置 a [i] 。我们高估的唯一子序列是之前 a [i] 附加的子序列，因此我们减去了这些子序列。Initially, we assume we can append a[i] to all subsequences ending on previous characters, but this might violate the condition that the counted subsequences need to be distinct. Remember that last[a[i]] gives us the last position a[i] appeared on until now. The only subsequences we overcount are those that the previous a[i] was appended to, so we subtract those.sum[i] = sum[i - 1] + dp[i]last[a[i]] = i根据定义更新这些值。如果索引从0开始，请使用 a [i-1] 在我使用 a [i] 的任何地方。另外，如果要提交代码，请记住将计算结果包装在 mod 函数中。应该这样实现：If your indexing starts from 0, use a[i - 1] wherever I used a[i]. Also remember to wrap your computations in a mod function if you're going to submit code. This should be implemented like this:mod(x) = (x % m + m) % m为了正确处理某些语言（例如C / C ++）中的负值。In order to correctly handle negative values in some languages (such as C/C++). 这篇关于如何找到一个字符串的不同子序列数？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！