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

CCC 2013, Day 2 Problem 3, Repetitivity
Автор ikbal, 10 лет назад, По-английски

There is a string with length n ≤ 104.

Let us denote fi as number of occurrences of the i'th unique sub sequence.

We need to calculate . Sub sequence does not have to be consective.

I have no idea about the solution so far. So any help would be appreciated.

Here is the source of the problem : link

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

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to count amount of different subsequences of a string?..

→ Ответить
  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Hint: For each distinct sub sequence count it when its lexicographically minimal by index values.

    → Ответить
»
10 лет назад, # |
  Проголосовать: нравится +24 Проголосовать: не нравится

Some magic: http://www.everfall.com/paste/id.php?tuo8fxsbhlx0.

The main idea is that desired sum may be obtained in the following way: let's iterate over all pairs of subsequences in the string S and do ans += 1 iff they are equal.

→ Ответить