6320: BZOJ2320:最多重复子串

Memory Limit:128 MB Time Limit:4 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

一个字符串P的重复数定义为最大的整数R,使得P可以分为R段连续且相同的子串。比方说,“ababab的重复数为3,“ababa的重复数为1。

Your Task

对于给定的串S,找出S的一个子串K使得K的重复数最大。


输入格式

第一行T表示数据组数

对于每组数据,一行中一个仅包含小写字母的字符串S


输出格式

对于每组数据,在一行中输出K,如果有多个解,输出字典序最小的那一个


样例输入

2
ccabababc
daabbccaa


样例输出

ababab
aa


提示

100%:T≤10,S的长度不超过100000


题目来源

没有写明来源

加入题单

上一题 下一题 算法标签: