[笔记]字符串同构与最小表示法

回忆起cf某场比赛的题目410 div-2 B,其实这题若存在方案,那么所有给定的字符串就是循环同构的字符串。但是我要说的和这题貌似没有太大的关系啦 其实只是举个循环同构的例子。

字符串的同构

如果两个字符串通过在同一个映射集合的一个或多个映射达成相同字符串,那么称这两个字符串是同构的。

最小表示法的算法实现

其实本身就不难吧

比如我们考虑2个字符串,如果它们是循环同构的,那么把一个字符串重复2次,一定可以在这个重复后的字符串中找到另一个串的匹配。这个可以用kmp算法实现。

但是我们考虑一些更为简单的算法,既然是循环同构的,那么我们记$start(k)$为该字符串从$k$位开始的循环表示是该字符串的最小表示(举例:$bbabcab$的$start(k)$为$6$,即$abbbabc$使所有循环表示中最小的),那么就可以我们对于两个字符串只需要找出各自的$start(k)$,再一一匹配就好了。

问题是如何找出$start(k)$呢?若中途匹配失败要返回重新找吗?

如果是后者,那么复杂度显然不在$O(n)$级别。于是考虑有没有方法避免重复比较。

可以发现,如果设有两个串$A$和$B$,那么假定开始的$start$指针分别在$i$和$j$,那么假定走了$x$位以后就匹配不了了:

若$A(i+x-1)>B(j+x-1)$,那么肯定对于$A$而言,最小的循环字符串不是从$start(i)$开始的。对$B$同理。

于是,只要匹配失败,我们只需要将对应字符较大的指针移向不匹配位的下一位即可。

那么判断匹配成功的条件就是成功地匹配了$length(A)$位了。这样能够保证算法复杂度在$O(n)$的样子。