特殊等价字符串组

记住这把钥匙：签名 = 排序后的偶数位 加 排序后的奇数位。下面每个串都现算它的签名，再看集合里有没有见过。

先把 4 个串摆出来。我们要逐个算签名、放进集合。集合现在是空的，0 组。

处理「abcd」。先看偶数下标 0 和 2，绿色这两个字符是 a 和 c，奇数位先灰着不动。

把偶数位的 a、c 排个序，得到 ac。这就是签名的前半截，顺序固定下来了。

再看奇数下标 1 和 3，绿色换到这两个字符 b 和 d，偶数位这回灰掉。

奇数位的 b、d 排序得 bd。前半 ac 接上后半 bd，「abcd」的签名就是 ac·bd。

拿 ac·bd 去集合里查，没见过，于是加进去，组数变成 1。

处理「cdab」。先看偶数下标 0 和 2，绿色这两个字符是 c 和 a，奇数位先灰着不动。

把偶数位的 c、a 排个序，得到 ac。这就是签名的前半截，顺序固定下来了。

再看奇数下标 1 和 3，绿色换到这两个字符 d 和 b，偶数位这回灰掉。

奇数位的 d、b 排序得 bd。前半 ac 接上后半 bd，「cdab」的签名就是 ac·bd。

拿 ac·bd 去集合里查，发现第 1 组里已有同款签名，「cdab」和它们特殊等价，并进去，组数不变还是 1。

处理「xyzz」。先看偶数下标 0 和 2，绿色这两个字符是 x 和 z，奇数位先灰着不动。

把偶数位的 x、z 排个序，得到 xz。这就是签名的前半截，顺序固定下来了。

再看奇数下标 1 和 3，绿色换到这两个字符 y 和 z，偶数位这回灰掉。

奇数位的 y、z 排序得 yz。前半 xz 接上后半 yz，「xyzz」的签名就是 xz·yz。

拿 xz·yz 去集合里查，没见过，于是加进去，组数变成 2。

处理「zzyx」。先看偶数下标 0 和 2，绿色这两个字符是 z 和 y，奇数位先灰着不动。

把偶数位的 z、y 排个序，得到 yz。这就是签名的前半截，顺序固定下来了。

再看奇数下标 1 和 3，绿色换到这两个字符 z 和 x，偶数位这回灰掉。

奇数位的 z、x 排序得 xz。前半 yz 接上后半 xz，「zzyx」的签名就是 yz·xz。

拿 yz·xz 去集合里查，没见过，于是加进去，组数变成 3。

4 个串算完，集合里留下 3 个不同签名。abcd 和 cdab 撞同一个签名归一组，xyzz 和 zzyx 各自单独一组（注意 xyzz 与 zzyx 并不等价），最终 3 组。

边界先想清：相同串并组；ab 与 ba 因 a、b 跨奇偶不可换，是两组。

两个常见追问：计数代替排序可提速；不等长的串签名必不同、天然分开。