题目:
We will call two words
本文中,将Manacher算法的“当前右边界”称为mx,i的回文半径称为R[i]。
“回文等价”的实质是什么呢?就是一堆相等和不等关系。为什么这么说?假设某个位置i的回文半径是R[i](我们淡化Manacher算法中那些#的影响,嗯,淡化),那么在某个和S回文等价的串T中一定有:T[i+1]=T[i-1],T[i+2]=T[i-2]……T[i+R[i]-1]=T[i-R[i]+1],以及T[i+R[i]]≠T[i-R[i]]。反过来,只要对于每个i都满足这些性质,S和T就一定回文等价。
但是这样的相等/不等关系太多了。怎么办呢?可以发现,实质不同的相等/不等关系都只有O(N)个。为什么这么说?我们考虑Manacher算法的过程。
先看相等关系。在Manacher算法的过程中,只有当i+R[i]越过mx时,超出mx的那些元素,和其对称位置的相等关系是新的。在其他情况下(即小于mx的情况),这个相等关系都等价于对称位置的相等关系。在i+R[i]越过mx之后,mx就更新成了i+R[i]。因而,我们想象mx连续地向右移动,每到一个新位置都可能产生一个新的相等关系。mx共移动至多N次,因此共有O(N)个本质不同的相等关系。
再看不等关系。每一位都只会产生一个不等关系(T[i+R[i]]≠T[i-R[i]]),自然一共有O(N)个不同的不等关系了!而且,还有很多不等关系与前边对称位置的不等关系相同,那就更少了(当然不影响O(N)这个结论)。
因此我们不妨想象这么一个算法:找出所有的相等和不等关系,将所有等价类合并,然后就转化成一张无向图(一定互异的两个等价类间连边),要求将顶点26染色,使得相邻点不同色,求方案数。
不过呢,这个图论问题是没有什么算法的……后面也没有用到图论的知识。虽然如此,这样说显得非常高端大气上档次,对吧。
然后我们再深入探讨一下这些相等/不等关系的特性。那个图论问题为什么不好解?原因大致是这样的:假设我们知道了顶点a和顶点b,c均不同色,但是并不知道b,c是否同色……那a的颜色到底有25种还是24种选择呢?这就麻烦了。
但是!这道题有一个美妙的性质。对应于刚才说的abc,我们一定知道b,c是否同色!换言之,如果我们知道T[i]≠T[j],T[i]≠T[k],其中k
这是为什么呢?(出题人:我就是这么吊。哈哈)不妨证明一下。
这样一来就好办了。算法需要干两件事:第一,标定等价类(不妨用等价类中最靠前元素的下标作为等价类的编号)。第二,确定哪些等价类之间不同。然后我们从前到后依次确定等价类。对于等价类i,如果有k个编号比它小的等价类(当然是去重后的)和它不相同,那么它就有26-k种选法。由于刚才证明的性质(这k个等价类必须显然一定总之不言而喻地两两不同),这种做法一定正确!
那么问题来了,挖掘机技术哪家强?不对,是怎么标定等价类和确定不等关系?
我们先思考等价类的确定方法。如果在之前的某个回文串中我们确定了T[j]=T[i],j
在越过mx时会发生什么呢?有两种越过mx的情况。
第一种是imx,由于i
第二种是i=mx(显然不会有i>mx,因为i=mx时就会立即越过mx)。这时,i明显不属于之前的任何一个等价类。那么,i就必然是一个新等价类的起点。然后我们就知道了0~i所在的等价类,在匹配过程中也就能知道0~i+R[i]-1(即0~新mx-1)所在的等价类。当然!这里淡化了Manacher算法在字符串中间加的那些’#’。如果S[i]是’#’,那它不属于任何等价类。
继续看如何确定不等关系。这就简单得多了。如果i+R[i]和i-R[i]都是字母,那我们就可以确定它们所属的等价类互异。根据刚才标记等价类的讨论,我们一定知道i-R[i]所属的等价类,但不一定知道i+R[i]所属的等价类。这无伤大雅:先用set存每个T[i]和哪些等价类互异,最后再把每个等价类的不等关系并在一起(对于等价类k,只保留编号比k小的那些不等关系)。
确定不等关系这里可以加一个优化:仅当i+R[i]>=mx时,我们才储存这一对不等关系。因为只有这时才会产生本质上的新不等关系。
最后,这道题的内存是64M……所以需要奇怪的卡内存。具体姿势见代码。