回文border理论
/ / 阅读耗时 21 分钟 对回文串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$，则有下面的性质成立：
- $|U|\geq |V|$。
- 若$|U|>|V|$，则$|U|>|Z|$。
- 若$|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
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;
}
例题
涉及回文border理论的字符串问题大多比较难，不过它们的重点都是要善于利用等差数列的性质。
[GYM102864I]shenyunhan Loves Palindrome
可以发现一段子串$[l,r]$合法的充要条件是：
- $[l,r]$是一个回文串
- $[l,r]$可以有两个非空回文串拼接组成
第一个很容易判，难的是第二个。
我们构建两个PAM，其中一个以正序顺序建立，另一个将串反串后建立。在回文树上倍增可以找到两段树链，分别为子串$[l,r]$的回文前缀以及回文后缀。现在问题转化为找两个节点，使得长度之和为$r-l+1$。
对于这个问题，朴素的算法最好也是$O(n)$的。但是使用回文border引理可以优化到$O(log^3n)$。
由于等差数列是$O(logn)$的，我们可以暴力地枚举两个树链上的等差数列，复杂度为$O(log^2n)$。然后用扩展欧几里得算法判定解的存在性即可，总体复杂度即为$O(nlog^3n)$。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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
using namespace std;
char op[N];
int n, q;
struct Node
{
int len, fa, ch[26];
};
struct Edge
{
int next, to;
};
struct PAM
{
Node nd[N];
Edge edge[N << 1];
int ct = 1, last, diff[N], slink[N], sdep[N], suf[N], head[N], cnt = 1, gr[N][20];
inline void addEdge(int x, int y)
{
edge[cnt].next = head[x], edge[cnt].to = y, head[x] = cnt++;
}
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], sdep[last] = sdep[nd[last].fa] + 1;
else
slink[last] = nd[last].fa, sdep[last] = 1;
}
void DFS(int x, int fa)
{
for (int i = head[x]; i; i = edge[i].next) {
if (edge[i].to == fa) continue;
gr[edge[i].to][0] = x;
for (int j = 1; j < 20; j++) gr[edge[i].to][j] = gr[gr[edge[i].to][j - 1]][j - 1];
DFS(edge[i].to, x);
}
}
void init()
{
nd[0].len = 0, nd[0].fa = 1, nd[1].len = -1, nd[1].fa = 0;
}
void insert()
{
for (int i = 1; i <= n; i++) add(op[i] - 'a', i), suf[i] = last;
for (int i = 2; i <= ct; i++) addEdge(nd[i].fa, i);
DFS(0, -1);
}
} pam1, pam2;
int gcd(int x, int y)
{
return y == 0 ? x : gcd(y, x % y);
}
int exGcd(int a, int b, int& x, int& y)
{
if (b == 0) {
x = 1, y = 0;
return a;
}
int t = exGcd(b, a % b, y, x);
y -= a / b * x;
return t;
}
int main()
{
scanf("%d%d%s", &n, &q, op + 1);
pam1.init(), pam1.insert();
reverse(op + 1, op + n + 1);
pam2.init(), pam2.insert();
while (q--) {
int l, r, len;
scanf("%d%d", &l, &r), len = r - l + 1;
r = pam1.suf[r], l = pam2.suf[n - l + 1];
for (int i = 19; i >= 0; i--) {
if (pam2.nd[pam2.gr[l][i]].len > len) l = pam2.gr[l][i];
if (pam1.nd[pam1.gr[r][i]].len > len) r = pam1.gr[r][i];
}
if (pam2.nd[l].len > len) l = pam2.gr[l][0];
if (pam1.nd[r].len > len) r = pam1.gr[r][0];
if (pam2.nd[l].len == len) {
printf("YES\n");
goto tag;
}
for (int i = l; i; i = pam2.slink[i]) {
for (int j = r; j; j = pam1.slink[j]) {
int res = pam2.nd[i].len + pam1.nd[j].len - len;
int d1 = pam2.diff[i], d2 = pam1.diff[j];
int d = gcd(d1, d2), x, y;
if (res % d == 0) {
res /= d, d1 /= d, d2 /= d;
exGcd(d1, d2, x, y);
x *= res, y *= res;
int down1 = ceil(1.0 * (y - pam1.sdep[j] + 1) / d1);
int up1 = floor(1.0 * y / d1);
int down2 = ceil(1.0 * (-x) / d2);
int up2 = floor(1.0 * (pam2.sdep[i] - x - 1) / d2);
if (up1 < down1 || up2 < down2) continue;
if (down1 > up2 || down2 > up1) continue;
printf("YES\n");
goto tag;
}
}
}
printf("NO\n");
tag:;
}
return 0;
}