Counting SubsequencesGiven a string, count all distinct subsequences (not substrings).
As defined previously, a subsequence is a collection of characters from the string (they don't have to be contiguous)
For example, for the string aba, there are 6 distinct subsequences: (a, b, aa, ab, ba, aba).
InputThe string, on one line. It will consist only of lowercase letters.
It will be no longer than 100,000 characters long (this is easier than all substrings!)
OutputThe number of distinct subsequences.
Note that this number may be ridiculously large, so print it mod 10,007.
Point Value: 10
Time Limit: 2.00s
Memory Limit: 16M
Added: Jun 27, 2013
- Dynamic Programming
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3