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

TIMUS 1960

Автор saba_tavdgiridze, история, 8 лет назад, По-английски

Hi , I was trying to solve this problem , which is about finding number of unique palindromic substrings in string of size n . As n can be large(10^5) ,only feasible is nlogn algorithm for this problem.Can you help me ? ( I was trying to solve with suffix array but don't succeed )

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

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

The problem is just a simple application of eertree (palindromic tree).

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

    I have known about this algorithm , but problem is one should't study every(and not so useful ) data structure for solving problems . It's better to know few and know it well.

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

      You don't need palindromic tree. This problem existed before palindromic trees became well-known. You only need to be familiar with Manacher's algorithm and maybe not even that, if O(N log N) passes .

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

There are my very old code for this problem, that using hashes: http://pastebin.com/SZmQFEL2

→ Ответить