poj3693 Maximum repetition substring

时间:2022-06-23 00:44:11
  • 题意
    给出一个长度为\(n(n\leqslant 100000)\)的串,求一个字典序最小的子串使得它是某个字符串重复\(k\)次得到的,且\(k\)最大
  • 题解
    后缀数组论文上的题,跟上一篇uva那个题做法有些相似。
    值得一提的是输出方案。
    在用前面的位置更新答案时,如果直接跨过一段区间,那么不能统计跨过的那一段中的子串,尽管他们长度一样,但字典序可能更优。
    于是有一种暴力:每次一直向前移,直到不匹配,在poj上跑出来时间跟下面的方法是差不多的。
    然后一个有复杂度保证的方法:更新答案时记录一下可能的循环串的长度,然后对于每个后缀,按照字典序检查是否满足条件。