I am in mood for kissing more
what I need is falling for you now,
On daisy you.
回文树的构造
简单讲一下,这个不是重点
考虑一个设一个奇根和一个偶根,分别存储奇回文串和偶回文串
类似 SAM ,我们依然可以考虑用以下几个信息来完成构建
- (fail) 指针
- (*ch) 数组
含义与 SAM 类似,至于如何构建,我们可以先把偶根的 (fail) 指向奇根, 然后因为字符串中本质不同的回文串是 (O(n)) 的,根据势能分析,暴力跳 (fail) 的时间也是 (O(n)) 的(每次深度最多加 1 ),所以直接暴力跳 (fail) 即可
模板:PAM模板
代码:
/*PAM(回文自动机)*/
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int read(){
char c = getchar();
int x = 0;
while(c < '0' || c > '9') c = getchar();
while(c >= '0' && c <= '9') x = x * 10 + c - 48,c = getchar();
return x;
}
const int N = 5e5 + 10;
struct PAM{
int len,fail,id;
int ch[26];
}pam[N<<1];
int ans[N],f[N];
char s[N];
int cnt = 1,now;
int getfail(int pos,int p){
while(s[pos - pam[p].len - 1] != s[pos]) p = pam[p].fail;
return p;
}
#define debug(x) cout<<x<<endl;
void ins(int pos){
now = getfail(pos,now);
int c = s[pos] - 'a';
if(!pam[now].ch[c]){
int x = ++cnt;
pam[x].len = pam[now].len + 2;
pam[x].fail = pam[getfail(pos,pam[now].fail)].ch[c];
f[x] = f[pam[x].fail] + 1; pam[now].ch[c] = x;now = x;
}else now = pam[now].ch[c];
ans[pos] = f[now];
}
int main(){
now = 1;
pam[0].len = 0,pam[0].fail = 1;/*偶根*/
pam[1].len = -1;/*奇根*/
scanf("%s",s+1);
int n = strlen(s + 1);
// s[0] = '%';
for(int i = 1; i <= n; ++i){
s[i] = (s[i] - 97 + ans[i-1]) % 26 + 97;
ins(i);
}
for(int i = 1; i <= n; ++i)
printf("%d ",ans[i]);
return 0;
}
最小回文划分
前置知识:
- 上文
- 基础的 border 理论
以下记 (s) ~ (t) 表示 (reverse(s) = t)
参考自:oi-wiki最小回文划分
以下介绍几个引理
- 若 (t) 是 (s) 的 border,且 (|s| leq 2|t|),那么 (s) 是 回文串,当且仅当 (t) 是回文串
(proof:)
设 (|t| = m), (|s| = n)
若 (t) 回文串,则 (s[1,m]) 回文, (s[n - m + 1,n]) 回文,设(|s[n-m+1,m]| = x), 注意到 (s[n-m+1,m]) ~ (s[1,x]),且 (s[n-m+1,m] = s[1,x]),
那么 (s[n-m+1,m])必然是回文的
中间一部分是回文的,两边是回文的,且相当,
那么整个串必然是回文的
若 (s) 是回文串,类似的可以证明 (t) 是回文串
主要是懒得画图,不画图说明又很麻烦
- (s) 的所有回文后缀按长度排序后,可以形成 (log|s|) 段等差数列
证明还是比较简单的,我们考虑所有回文后缀都是最长回文后缀的 border ,然后根据 border 的理论,可以划分成 (log|s|) 段等差数列
首先考虑朴素方程
(dp_i = 1 + min{dp_j}[s[j+1,i] is palindrome])
为了方便辨识等差数列,我们令 (dif(x) = len(x) - len(fail(x))), (slink(x)) 为该等差数列的首项(同时也是下一个等差数列的最后一项)所在的位置
我们用 (g(x)) 来保存 (x) 所在的等差数列所有的答案
考虑增量法,我们不妨思考 (g(x)) 和 (g(fail(x))) 的关系
-
若 (dif(x) = dif(fail(x))),则这两个同处一个等差数列,根据引理 (1) , (fail(x)) 是 (x) 的 (border) , 即既是后缀也是前缀,(接下来不太好解释,可以参考 oi-wiki 的图),那么我们可以认为 (g(fail(x))) 的代表的所有回文串都向后移动了 (dif(x)),那么可以发现新增的 (dp) 值只有该等差数列首项上面的那个回文串,其长度为 (dif(x) + len(slink(x))),用其更新即可
-
否则的话,那么 (g(x)) 仅需存储本身的长度,本身的长度即为 (len(x)) , 注意到此时 (len(x) equiv len(slink(x)) + dif(x))
暴力跳 (slink) 即可,复杂度 (O(nlog n))
例题:CF932G
代码:AC code