目录
Description
给出一个字符串，定义 \(f(t)=max(next[i]), {\{1<=i<=|t|}\}\)， 其中 \(next[]\) 表示 \(kmp\) 算法中的数组；
将 \(t\) 重新组合之后，得到的字符串 \(s\) ，使得 \(f(s)\) 最小，如果有多组，输出字典序最小的哪一个 \(s\)
State
\(1<=T<=10^5\)
\(1<=|t|<=10^5\)
Input
3
vkcup
abababa
zzzzzz
Output
ckpuv
aababab
zzzzzz
Solution
1.如果只有一种字符构成的字符串，那么答案就是原串
2.首先如果所有字符都只有 一个，那么 \(f(s)=0\) ，只要输出字典序最小的那个就好
3.如果有字符出现了不止 1 次，首先想要保证 \(f(s)\) 最小，如果有字符出现了 1 次，依旧可以保证 \(f(s)=0\)
4.但如果出现的字符都不知出现一次，那么不可避免地 \(f(s)>0\);
4.1：找到字典序最小的字符记为 \(a\)，如果可以满足 \(aababacaca\) 的情况最好；但是 \(aababacacaaaaa\) 这样就需要调整了
4.2：如果只有两种字符，那么答案可以写成 \(abbbbbaaaaaa\)，这是为了避免出现 \(ab\)
4.3：但是如果字符过多，\(abaaaacbbbbbbccc\) ，这样同样可以避免出现 \(ab\) 的情况，而且字典序还更小