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

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

I'm reading "Lyndon factorization" topic by the link below, and be stuck by the term "nontrivial suffixes". I googled but it does not help much. Can guys help me figure it out ? Thanks a lot !

https://cp-algorithms.com/string/lyndon_factorization.html

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

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

Non trivial is same as non empty.

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

    Thank you ! But that topic said that: " A string is called simple (or Lyndon word), if it is "strictly" smaller than any of its own nontrivial suffixes. Example of simple string is "aab" " So nontrivial prefixes of "aab" are "a", "aa" and "aab" , but "aab" not strictly smaller than "aab"

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

      Okay I missed that, because what non trivial really means, is not an obvious thing. Like empty suffix and full suffix are obviously not strictly smaller, and we just ignore those trivial things.