Блог пользователя kitsune

Автор kitsune, история, 4 года назад, По-английски

You are given a string $$$s$$$ with length $$$N$$$ and in this problem you should find the number of unique subsequences (not substrings) of the string of every length. eg. find the number of unique subsequences of length $$$1,$$$ then length $$$2, 3 ... N$$$. Answer can be big so print it modulo $$$1e9+7$$$. If the statement is confusing please, see the "explanations" below. I found this post on geeksforgeeks but it counts the total number of distinct subsequences.

Length of the string $$$N<=1000$$$

Example:

Input:

$$$s = dpdp$$$

Output:

$$$2$$$ $$$4$$$ $$$4$$$ $$$1$$$

Explanation:

there are two subsequences of length 1: $$${d, p}$$$

4 subsequences of length 2: $$${dp, dd, pd, pp}$$$

4 subsequences of length 3: $$${dpd, pdp, dpp, ddp}$$$

1 subsequence of length 4: $$${dpdp}$$$

I think it's very easy problem but I have no idea how to solve it. Thanks in advance.

Sorry for my poor English.

Полный текст и комментарии »

  • Проголосовать: нравится
  • +5
  • Проголосовать: не нравится