加密把 26 个小写字母分成若干个大小至少为 2 的环(置换),对原串 s 中每个字母换成其所在环的下一个字母得到 t。
因此对每个出现于 t 的字母 y,原串对应位置的字母一定是 y 在环中的前驱,记为 pre[y];同时每个字母作为前驱最多用一次,记为 to[x] 表示 x 的后继。
目标:构造映射 pre / to,使得按 s[i] = pre[t[i]] 得到的 s 字典序最小,并且这组部分映射能扩展成“所有 26 个字母组成的、环长≥2 的置换”。
对于一个由小写字母组成的字符串 s ,我们可以按以下方式将其加密成字符串 t :
将所有 26 个小写字母任意分成若干个大小至少为 2 的环,每个字母恰好属于一个环;
对于原串中的每个字母,将其替换为所在环中的下一个字母。
这样可以得到加密后的字符串 t 。