回文border理论

        对回文串border理论的初探。本文需要回文自动机前缀知识。

        为了方便叙述,我们用$S$表示一个字符串,用$|S|$表示其长度,$S[i],1\leq i \leq |S|$表示其第$i$个字符。

border

        对于一个字符串$S$,我们记$pre(S,i)$为其长度为$i$的前缀,即$S[1…i]$,记$suf(S,i)$为长度为$i$的后缀,即$S[|S|-i+1…|S|]$。如果$1\leq i< |S|,pre(S,i)=suf(S,i)$,我们称$pre(S,i)$为字符串$S$的border。
        如果对于$0<t\leq |S|$,若$\forall i,1\leq i\leq|S|-t$,有$S[i]=S[i+t]$,则称$t$为$S$的周期。
        关于border与周期,有如下的定理:

  • 【定理1】$T$是$S$的border的充要条件是$|S|-|T|$为$S$的周期。

证明:
        充分性:若$|S|-|T|$是$S$的周期,则对于$\forall i,1\leq i\leq |T|$,有$S[i]=S[i+|S|-|T|]$,这显然说明$pre(S,|T|)=suf(S,|T|)$,即$T$是$S$的border。
        必要性:若$pre(S,|T|)=suf(S,|T|)$,则有$\forall i,1\leq i\leq |T|$有$S[i]=S[i+|S|-|T|]$,从而得到$|S|-|T|$为$S$的周期。

回文border的相关理论

        了解了border的定义后,我们会证明一个重要的定理:

  • 【定理2】对于字符串$S$,将其所有回文后缀按长度排序后,可以划分为$log|S|$段等差数列。

        在证明这个理论之前,先引入四个引理:

  • 【引理2.1】对于回文串$S$,$T$是$S$的后缀,则$T$是$S$的border的充要条件是$T$是回文串。

证明:
        若$T$是回文串,则$\forall |S|-|T|+1\leq i\leq |S|,S[i]=S[2|S|-|T|+1-i]$。又根据$S$是回文串,可以得到$S[i]=S[2|S|-|T|+1-i]=S[|S|+1-i]=S[|T|-|S|+i]$,这就证明了$pre(S,|T|)=suf(S,|T|)$,从而$T$是$S$的border。同理可证必要性。

  • 【引理2.2】对于字符串$S$及其border$T$,若$|S|\leq 2|T|$,则$S$为回文串的充要条件是$T$为回文串。

证明:
        $\forall i,1\leq i\leq |T|$,根据$T$为border且为回文串有:

        这就证明了$1\leq i\leq |T|$时,$S$符合回文串性质。由于$|S|\leq 2|T|$,可知$|T|\geq \frac {|S|}{2}$,从而$S$就是回文串。
        必要性同理。

  • 【引理2.3】对于回文串$S$,$|S|-|T|$为$S$的最小周期的充要条件是$T$是$S$的最长回文真后缀。

证明:
        首先根据定理1可知$|S|-|T|$是最小周期等价于$T$是$S$的最长border。
        由于$T$是回文后缀,则根据引理2.1,$T$是$S$的border。并且由于$T$是最长回文真后缀,可知$T$为最长border。必要性根据引理2.1可以反向推知。

  • 【引理2.4】对于回文串$X$,其最长回文真后缀为$Y$,$Y$的最长回文真后缀为为$Z$,设字符串$U,V$满足$X=UY,Y=VZ$,则有下面的性质成立:
  1. $|U|\geq |V|$。
  2. 若$|U|>|V|$,则$|U|>|Z|$。
  3. 若$|U|=|V|$,则$U=V$。

证明:
        对于性质一,我们采用反证法,我们用$\overline S$来表示$S$的翻转。假设$|V|>|U|$。由于$Y$是回文串,必有$VZ=Z\overline V$,并且因为$X$为回文串,可知$UVZ=UZ\overline V=VZ\overline U$,由此可知$U$为$V$的前缀,不妨令$V=US$,这里$|S|>0$。那么由于$X$为回文串,可得$UVZ=UUSZ=Z\overline S \overline U\overline U$,由$Y$是回文串可得$VZ=USZ=Z\overline S\overline U$。于是可得$UZ\overline S\overline U=Z\overline S\overline U\overline U$,即$UZ\overline S=Z\overline S\overline U=USZ$,从而$Z\overline S=SZ$,这样我们就得到了比$Z$更长的回文后缀$SZ$,这与$Z$为$Y$的最长回文后缀矛盾,因此必有$|U|\geq |V|$。
        性质二同样采用反证法。由性质一中证明的思路,我们可以发现$|U|>|V|$时,$V$为$U$的前缀,不妨设$U=VP$,然后假设$|U|\leq |Z|$。根据$UZ\overline V=Z\overline V\overline U$,可知$U$为$Z$的前缀,不妨设$Z=US,|S|\geq 0$,这样经过代入,可以得到$UUS\overline V=US\overline V\overline U=US\overline V\overline P\overline V$,从而有$US=VPS=S\overline V\overline P=Z$。由于$Z$是回文串,故$S\overline V\overline P=PV\overline S=VPS$,所以$PV=VP,S=\overline S$。于是:

        由此我们得到了$PY$这个比$Y$更长的回文后缀,这与$Y$为最长回文后缀矛盾。从而性质二成立。
        性质三从上面证明中可以发现显然成立。

        我们现在来证明定理2。在这里我们仍用引理2.4的串$X,Y,Z$来说明。
        注意到等差的条件就是$|U|=|V|$,根据引理2.4我们只需要证明$|U|>|V|$的次数在$log|S|$级别即可。由于$|U|>|V|$,有$|U|>|Z|$,于是$2|U|>|V|+|Z|=|Y|$,即$|Y| < 2|U|=2(|X|-|Y|)$,从而有$|Y|<\frac {2|X|}{3}$,那么$|U|>|V|$的出现次数必然在$log_{1.5}|S|$级别,证毕。

border理论在PAM上的应用

        border理论究竟有什么用,我们至今还没有提及。事实上border理论是一个将一些在PAM上的问题的复杂度降为$O(nlogn)$的理论基础。
        考虑最小回文划分问题:给一个字符串$S$,求一个划分$S_1+S_2+\cdots+S_k=S$,使得$S_i$为回文串,最小化$k$。对于这个问题,我们可以考虑$DP$,用$f(x)$表示前$x$位的答案,然后状态转移方程为:

        建出PAM后,我们可以在某一个节点的回文后缀上进行转移,这样就可以在$O(n^2)$的复杂度下解决这个问题。利用border理论的定理2,这个复杂度可以降为$O(nlogn)$。
        利用等差数列段数在$log|S|$级别这个性质,我们可以维护一段等差数列的信息,从而只需要进行$log|S|$次转移,从而降低复杂度。
        在PAM上,每一个节点需要多维护两个信息$diff[x]$以及$slink[x]$,其中$diff[x]$表示其与$fail[x]$即最长回文真后缀的长度差,即$len[x]-len[fail[x]]$。而$slink[x]$表示向上的第一个节点$u$使得$diff[x]\not=diff[u]$,这样$x$到$slink[x]$这些回文串的长度差都是相同的。我们将$DP$的信息放到每一段等差回文串中最长的那一个串节点上。
        我们给每一个节点再维护一个$g[x]$数组,当枚举到第$i$个字符时,定义如下:

        注意$slink[x]$算到下一个等差数列中。
        每一次枚举$i$,都需要更新$g$数组和$f$数组,考虑如何更新。
        假设当前枚举到了$i$,对应的节点是$x$,可以发现$fail[x]$对应的串上一次出现的位置必然是$i-diff[x]$,那么根据$g$的定义,$g[fail[x]]$为:

        考虑到$g[x]$应该为:

        我们假设$g[fail[x]]$维护的序列按长度降序排序是$fail[x]\cdots p$,这里显然$fail[p]=slink[fail[x]]$。假设$len[x]-len[p]=ndiff[x]$,那么$g[fail[x]]$可以表示为:

        注意到此时$g[x]$可以表示为:

        两者比较可以发现:

        $len[p]$显然等于$len[slink[x]]+diff[x]$,那么就有:

        这样我们就得到了利用已有的$g$数组更新的方法,于是向上跳$slink[x]$,就可以完成更新。
        这里给出利用border理论完成的最小回文划分问题代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <bits/stdc++.h>

#define N 500005
using namespace std;
struct Node
{
int len, fa, ch[26];
} nd[N << 1];
int ct = 1, last, diff[N], slink[N], dp[N], g[N];
char op[N];

inline int newNode(int x)
{
int p = ++ct;
nd[p].len = x;
return p;
}

inline void add(int c, int pos)
{
int u = last;
while (op[pos - nd[u].len - 1] != op[pos]) u = nd[u].fa;
if (nd[u].ch[c] == 0) {
int s = newNode(nd[u].len + 2), f = nd[u].fa;
while (op[pos - nd[f].len - 1] != op[pos]) f = nd[f].fa;
nd[s].fa = nd[f].ch[c], nd[u].ch[c] = s;
}
last = nd[u].ch[c];
diff[last] = nd[last].len - nd[nd[last].fa].len;
if (diff[last] == diff[nd[last].fa]) slink[last] = slink[nd[last].fa];
else slink[last] = nd[last].fa;
}

int main()
{
nd[0].len = 0, nd[0].fa = 1, nd[1].len = -1, nd[1].fa = 0;
scanf("%s", op + 1);
for (int i = 1; op[i]; i++) {
add(op[i] - 'a', i), dp[i] = 0x7fffffff;
for (int j = last; j > 1; j = slink[j]) {
g[j] = dp[i - nd[slink[j]].len - diff[j]];
if (diff[j] == diff[nd[j].fa]) g[j] = min(g[j], g[nd[j].fa]);
dp[i] = min(dp[i], g[j] + 1);
}
}
printf("%d", dp[strlen(op + 1)]);
return 0;
}

0%