C - K-th Substring

  • image
  • 考えたこと
    • 接尾辞配列を作る?
    • 文字列長さが高々5000だから普通のソートでもいけそう
    • Kが5までとやたらに小さい
    • 接尾辞配列の1行目でK個取れない場合はLCP分を飛ばして次の行へ
  • 公式解説
    • だいぶ方針が違う
    • すべての部分列を列挙して、ソート、uniq
    • それだと遅いのでK以下のものしか出ないことを利用して候補を減らす
    • 接尾辞配列の方針でできるならそっちの方が軽いのでは