学步园

【任务】

给定一个环形的字符串s，求字符串t，使得t是所有与s长度相同的子串里字典序最小的字符串。

（同USACO 5.5.2 hidden）

【思路】

显然，这两个字符串是循环同构的。

怎么做？O(n^2)枚举？也许对于随机数据，枚举的均摊时间复杂度接近线性，但如果对于"aaaaaaaaaaaaab"这样的数据以及n为几十几百万的时候，只能TLE了。

至于利用KMP的匹配算法，当然也不错，可以通过巧妙的构造、转换模型，直接套用模式匹配算法，得到O(n)级的算法。

但……KMP作为一个算法没有任何缺陷？

对于神犇和教主级别的的人物当然没有，但对于我这种苣蒻……KMP实在是有种难理解，难记忆的赶脚。

更要命的是，限于失配函数的限制，KMP的扩展性也不强。

怎么办？作为一种解决同构问题十分优秀的思想方法，最小表示法表示毫无压力。

容易知道，当两个对象有多种表达形式，且需要判断它们在某种变化规则下是否能够达到一个相同的形式时，可以将它们都按一定规则变化成其所有表达形式中的最小者，然后只需要比较两个“最小者”是否相等即可！

比如两列数，不计顺序，问是否相同。

不计顺序？那岂不是有n!种变换可能？会爆？

再仔细想一想，只要比较它们的有序形式不就行了么？

也许你之前并不知道最小表示法，但只要学过OI就一定能想出上面的简单问题！而这就是一个最小表示法的应用！

因为我们引入了“序”这个概念，从而将纷繁的待处理对象化为单一的形式，便于比较。

（1）任意t∈T，一定能在F中一系列映射的连接的作用下，仍被映射至t。即任意一个事物t∈T，它和自己是F本质相同的。

（2）任意s,t∈T，若在F的一系列映射作用下，s和t是F本质相同的。那么一定有另一系列属于F的映射作用下，t和s是F本质相同的。

综合以上，再根据“本质相同”概念的定义很容易知道，本质相同这个概念是一个等价关系。

有了最小表示法这个针对同构问题的思想方法，这道题我们怎么处理呢？

对于给定的一个串，将它的所有后缀按字典序排序，其中第一个后缀就是最小后缀。对于一个长度为n的主串s，设v[i]表示子串s[i..i+v[i]-1]，该子串的所有前缀在主串中所有相应长度的子串中字典序最小。

比如对于串acab则v[3]=2，即子串"ab"的所有前缀("a","ab")中，"a"在所有长度为1的子串("a","c","b")中字典序最小，"ab"在所有长度为2的子串("ac","ca","ab")中字典序最小。

我们要求的是最大的v[i]，则i开始的主串的后缀就是最小后缀。

初始时v为0。设list记录当前所有的i，使得v[i]当前最大，初始时list=(1..n)。

对于每个在list中的i，如果v[i+v[i]]>0，那么把s[i..i+v[i]-1]和s[i+v[i]..i+v[i]+v[i+v[i]]-1]合并后的s[i..i+v[i]+v[i+v[i]]-1]肯定最小，则v[i]=v[i]+v[i+v[i]]。同时为了避免重复，把i+v[i]从list中去掉。

如果v[i+v[i]]=0，那么当且仅当s[i+v[i]]在所有s[j+v[j]]（j在list中）中最小时，v[i..i+v[i]]才最小，则v[i]=v[i]+1。

求出v后，把当前v最大的i放入list，其余的删掉，重复这个过程，直到list中只有1个i为止。

可以看出以上过程实际上就是不断地合并区间，而每个位置最多只访问一次，list中的位置最多删除一次，所以总的复杂度是O(n)的。

我们把主串复制两份，这样就解决了圈的问题。然后我们在串的最后加一个大于串中所有字符的字符（'z'+1），因为事实上对于这道题，输入"aaa"，应输出0。

此时这个串的最小后缀所对应的开始位置i就是所求。因为最小后缀的前缀肯定是最小的。

可以看出，“最小表示法”是判断两种事物本质是否相同的一种常见思想，它的通用性也是被人们认可的——无论是搜索中判重技术，还是判断图的同构之类复杂的问题，它都有着无可替代的作用。