Wednesday, August 6, 2014

Counting Subsequences

Problem Link(PEG Judge)

Given 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).

Input

The 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!)

Output

The number of distinct subsequences.
Note that this number may be ridiculously large, so print it mod 10,007.

D(i) = "i번째에서 끝나고, i번째 문자를 반드시 넣을 때 만들어지는 
distinct subsequences의 개수"라고 정의하자.

i번째 문자를 S(i)라고 하자. S[i] = S[j](j<i)인 j중 가장 큰 j에 대해서 D[i] = Sum(D[j] ~ D[i-1])

만약 S[i]가 처음 등장했다면, D[i] = Sum(D[1]~D[i-1])+1이 된다.

Source Code

No comments:

Post a Comment