周期、borders

· · 个人记录

周期：称p为字符串S的一个周期，当且仅当对于任意的1\leq i\leq |S|-p都有S_i = S_{i+p}

弱周期引理：若p，q是S的周期，且p+q\leq |S|，那么gcd(p,q)也是S的周期

用辗转相减法容易证明（S_i = S_{i+p}=S_{i+q}=S_{i+p-q}）

强周期引理：若p，q是S的周期，且p+q-gcd(p,q)\leq |S|，那么gcd(p,q)也是S的周期

border：S的一个前缀等于后缀，则该前缀是一个border，border\neqS

可以发现KMP算法的next数组就是每一个前缀的最长border

两者的关系：如果p为S的周期，那么存在长度为|S|-p的border，反之亦然

匹配与等差数列

引理1：如果\frac{|S|}{2}\leq |T|，那么T在S中的所有匹配位置是一个等差数列

证明：考虑至少有三次匹配的情况；设第一个匹配和第二个匹配的间隔为d，第二个匹配与后面某一个匹配的间隔为p；因为T长度“过半”，所以用周期和border之间的关系可以知道d和q都是T的周期，那么gcd(d,q)也是T的周期，由于d\leq gcd(d,q)（否则第一个和第二个匹配的间隔应为gcd(d,q)），所以d=gcd(d,q)，即有d|q，引理得证

同理也可以在知道匹配位置的情况下推出T的最小周期（注意前提是至少有三次匹配）

引理2：如果border的长度过半，那么border的位置是一个等差数列

证明类似上面，证明整除关系即可

对于未过半的border可以递归S的右一半，对于新的一半中的过半border，可以证明它们都是最长的那个过半border的过半border（左一半得出前缀相等，右一半得出后缀相等）

于是可以递归处理所有border

推论：所有的border从小到大排序最多有logn个等差数列

和回文串的联系

如果S是回文串，那么T是S的回文后缀当且仅当它是一个border

于是有些回文后缀的题也可以用上面的等差数列来搞了