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