poj3693 Maximum repetition substring

2024-01-22 18:33:10

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