萌新刚学 OI 求助字符串题

定义 $S\prec T$，当且仅当 $S+T<T+S$。给定字符串 $A$，将 $A$ 分解成 $S_1+S_2+\dots+S_k$ 的形式，满足 $\forall1\le i<k,S_i\prec S_{i+1}$，且 $|S_i|$ 组成的序列字典序最小。$|A|\le10^6$。

怎么做怎么做/kel