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

Help or insight into CSES String Transform Problem
Автор upobir, история, 4 года назад, По-английски

I was happily browsing internet 2 days ago until I saw this problem String Transform. Been stuck at it for two days now, and the best I could come up with is a rough $$$O(n^2)$$$ idea. Would be greatful for some hints.

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

»
4 года назад, # |
← Rev. 2   Проголосовать: нравится -6 Проголосовать: не нравится

It can be solved using suffix array. If you don't know what it is there a course in the edu section.

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

    I know suffix array, but the application here isn't obvious to me. I have all rotation's last character, which is a permutation of the original string, so computing this string's suffix arrays shouldn't be useful, right? So what do I build the suffix array of?

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

      You can just build the suffix array of the original string. Then replace every character of the original string with the one before (so this is the last character of the string starting at this position), and sort this new string based on the suffix array.

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

        But I do not have the original string? For example in the sample I am given "cb#ab" the final string, I have to restore the original string myself. Or by original string are you referring to the input string?

        → Ответить