HDU 2459 PKU 3693 Maximum repetition substring 后缀数组 RMQ

题目地址：

HDU 2459 PKU 3696

题意：

给一个长度不超过1e5$1e5$的字符串，找出其中一个子串，要求该子串能够被分割成尽可能多的相同的字符串，若有多个符合要求的子串，输出字典序最小的那个。

思路：

图片不看也没关系，但这个是罗穗骞大佬在他的论文《后缀数组——处理字符串的有力工具》里的原话，然后这是他的spoj687的代码：http://paste.Ubuntu.com/23923746/，本人就是参考他的代码，明白了思路的

RMQ部分只是用来求lcp的，不说了 枚举子串重复部分的长度L，然后以L为步长，枚举题目所给的字符串下标，设lcp是suffix[L]和suffix[2 * L]的公共前缀，只要lcp>=L$lcp>=L$，重复的字符串就出现了（首先两者相同的部分超过了suffix[L]和suffix[2 * L]的距离，然后suffix[2 * L]作为suffix[L] 的子串，重复lcp部分，就构成了一个有重复的字符串，可能这里有点绕……不懂的读者可以自己举例理解下）。 重复部分的重复次数自然就是lcp/L+1$lcp / L + 1$（两字符串公共部分的长度 / 重复部分的长度 + suffix[L]到suffix[2 * L]之间的子串个数） 然后考虑一个特殊情况，比如说如下字符： 0123123123 就是按上述方法计算的话，算出来的字符是312312，原因是因为枚举时出了问题（毕竟不是一个个枚举的，而是有步长的枚举），考虑suffix[3]与suffix[L]的lcp长度为4，比枚举的长度3多了一个1，可以往前再走L−lcp$L - lcp % L = 2$步（1+2==3$1 + 2 == 3$），看看这个后缀与其后面L的后缀的lcp长度是否大于等于L−lcp$L - lcp % L$，如果比前面走的步数要大的话，说明少计算了一次重复部分。 输出答案的部分参考了cxlove的，本来自己是特判加枚举子串时直接判定答案的，可以不知道哪里写丑了，总是有问题，后面就换成了cxlove的思路QAQ，他的题解：http://blog.csdn.net/acm_cxlove/article/details/7941205

可能说的不好，还请读者多多思考

代码：