本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-07-29 22:06:12

纪念第一次赛时过 Ex && 做出 atc 2400+ 题目，虽然是个大水题。

• 做法 $1$
  考虑暴力枚举 $k$，暴力判定。
  显然会寄掉。

• 做法 $2$
  显然同一个字符串出现两次，第二次的答案一定大于第一次。
  其实一个字符串，只会对所有的循环节产生影响，而它本身的循环节种类显然是 $O(\sqrt{n})$ 量级的，可以参考因数数量，设本字符串长度为 $len$，那么最终造成的时间消耗是 $O(len \sqrt{len})$ 级别的。
  复杂度瓶颈在于同一个字符串出现多次。
  所以可以对字符串进行记忆化，对输入的字符串存储答案字符串，对最终形成的字符串（答案字符串）进行存在性标记。
  但朴素实现复杂度不变，主要瓶颈在于存储最终的答案字符串。

• 做法 $3$
  考虑字典树，此时我们对于答案字符串的记忆化，不再直接存储字符串，转而使用字典树，而记忆方式则是同时记录 $k$ 和答案字符串对应的字典树坐标。
  这样构造当前答案的时候，可以直接从原记录的字典树对应位置继续构造，而不用从头开始。
  复杂度 $O(len \sqrt{len})$。
  AC code
  另外由于循环节数量实际上一般远远少于根号，所以运行时间应该是接近 log 的。