Category Archives

420 Articles

信息学奥林匹克竞赛

「2021 CCPC 桂林」J – Suffix Automaton

Posted by Kalorona on

简要题意

给定一个字符串 \(S\)。对该字符串本质不同的子串定义一种排序方式:

  • 长度不同时,长度短的排在低次位。
  • 长度相同时,按字典序排序。

简单而言,长度是第一关键字,字典序是第二关键字。现在给定 \(Q\) 个询问,每个询问要求找到在该排序下排名为 \(k\) 的子串的第一次出现位置。

数据范围

\(1 \leq |S|, Q \leq 10^6, 1 \leq k \leq 10^{12}\)