基础
P3649 [APIO2014]回文串
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
| const int N=300010;
int n,m,tot,cnt[N],len[N],fail[N],last,son[N][27],cur;
char s[N];
ll ans;
namespace PAM{
inline int new_node(rei x){
len[tot]=x; cnt[tot]=0;
return tot++;
}
inline int get_fail(rei x,rei now){
while(s[ now-len[x]-1 ]!=s[now]) x=fail[x];
return x;
}
inline void build(){
for(rei i=1;i<=n;++i){
rei x=s[i]-'a';
cur=get_fail(last,i);
if(!son[cur][x]){
rei now=new_node(len[cur]+2);
fail[now]=son[ get_fail(fail[cur],i) ][x];
son[cur][x]=now;
}
last=son[cur][x];
++cnt[last];
}
}
inline void sumup(){
for(rei i=tot-1;i>=0;--i) cnt[ fail[i] ]+=cnt[i],ans=max(ans,(ll) cnt[i]*len[i]);
}
}
int main(){
scanf("%s",s+1);
n=strlen(s+1);
PAM::new_node(0); PAM::new_node(-1);
fail[0]=1; last=0;
PAM::build();
PAM::sumup();
printf("%lld\n",ans);
getchar(),getchar();
return 0;
}
|
应用
本质不同的回文串个数
$tot-2$ 即可
所有回文子串出现次数
按拓扑序将每个节点的最长回文后缀的出现次数加上该节点的出现次数
1
2
| for(rei i=cnt;i>=2;--i)
sum[ fail[i] ]+=sum[i];
|
以当前节点结尾的回文子串个数
设 $num_i$ 表示节点 $i$ 的回文子串个数，由于 new_node 操作建立的节点 $x$ 就是在 $fail_x$ 左右各加一个相同字符，则有 $num_x=num_{fail_x}+1$
build 的时候动态求即可
双倍回文后缀
引入 $trans$ 指针：小于等于当前节点长度一半的最长回文后缀
做法显然：
- 对于 $len\leq 2$ 的串， $trans$ 指针指向其 $fail$ 节点
- 从其父亲的 $trans$ 指针开始跳 $fail$ ，直到跳到满足长度且左右能拓展当前字符的节点，将 $trans$ 指针指向该节点的儿子
1
2
3
4
5
6
7
8
9
10
11
| inline void extend(int x,int i){
...
if(len[now]<=2) trans[now]=fail[now];
else{
rei tmp=trans[cur];
while(s[ i-len[tmp]-1 ]!=s[i] || ((len[tmp]+2)<<1)>len[now]) tmp=fail[tmp];
trans[now]=son[tmp][x];
}
...
}
|
例题
求串 $S$ 的最长双回文子串 $T$ 使 $T$ 可以分成 $X,Y$ ，其中 $X,Y$ 都是回文串
考虑 $last$ 的含义：以当前加入字符结尾能得到的最长回文串的节点号，记录 $l_i=len_{last}$ 就表示以 $i$ 字符结尾的最长回文串长度
做两次回文自动机，一正一反，那么 $l_i+r_{n-i}$ 就是两最长回文串拼起来的结果
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
| namespace PAM{
...
inline int get_fail(int x,int n,int op){
if(op){
while(s[ n-len[x]-1 ]!=s[n]) x=fail[x];
return x;
}
else{
while(rev[ n-len[x]-1 ]!=rev[n]) x=fail[x];
return x;
}
}
inline void extend(int x,int i,int op){
cur=get_fail(last,i,op);
if(!son[cur][x]){
rei now=new_node(len[cur]+2);
fail[now]=son[ get_fail(fail[cur],i,op) ][x];
son[cur][x]=now;
}
last=son[cur][x];
op ? r[i]=len[last] : l[i]=len[last];
}
...
}
int main(){
...
for(rei i=1;i<=n;++i) rev[i]=s[n-i+1];
PAM::new_node(0); PAM::new_node(-1);
fail[0]=1; last=0;
for(rei i=1;i<=n;++i) PAM::extend(rev[i]-'a',i,0);
PAM::clear();
PAM::new_node(0); PAM::new_node(-1);
fail[0]=1; last=0;
for(rei i=1;i<=n;++i) PAM::extend(s[i]-'a',i,1);
for(rei i=1;i<=n-1;++i) ans=max(ans,l[i]+r[n-i]);
...
}
|
求多少对相交的回文子串(包含属于相交)
容斥( 正难则反
求所有回文子串对数减去不相交的
设 $l_i$ 表示从 $i$ 开始的回文串个数，$r_i$ 表示从 $i$ 结束的回文串个数
与上题相同，正反构造两次回文自动机
不相交的即为：$\displaystyle{\sum_{i=1}^{|S|} r_i \sum_{j=i+1}^{|S|}l_j}$
每个节点到根节点的距离(深度)，就是回文后缀的数量
注意这个题的空间比较紧，所以考虑用邻接表替代 $son$
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
| namespace PAM{
inline void init(){
for(rei i=0;i<=tot_pam;++i) head[i]=0,fail[i]=len[i]=0;
tot_line=0,last=0; len[tot_pam=1]=-1; fail[0]=fail[1]=1;
}
inline int get_son(int k,int c){
for(rei i=head[k];i;i=Next[i]) if(val[i]==c) return ver[i];
return 0;
}
inline void extend(...){
...
if(!...){
...
depth[now]=depth[ fail[now] ]+1;
add(cur,now,x);
...
}
}
}
int main(){
...
PAM::init();
for(rei i=1;i<=n;++i){
PAM::extend(s[i]-97,i,s);
ans=(ans+(r[i]=depth[last]))%mod;
}
ans=(ll) ans*(ans-1)/2%mod;
reverse(s+1,s+n+1);
memset(depth,0,sizeof depth);
PAM::init();
for(rei i=1;i<=n;++i){
PAM::extend(s[i]-97,i,s);
l[n-i+1]=depth[last];
}
for(rei i=n;i;--i) (l[i]+=l[i+1])%=mod;
for(rei i=1;i<=n;++i) ans=(ans-(ll) r[i]*l[i+1]%mod+mod)%mod;
...
}
|
求双串的最长公共回文串
分别建两个回文自动机，最后从奇偶根开始搜索相同状态即可
1
2
3
4
5
| void dfs(int l,int r){
if(MAX<pam1.len[l]) MAX=pam1.len[l],ans=1;
else if(MAX==pam1.len[l]) ++ans;
for(rei i=0;i<26;++i) if(pam1.son[l][i] && pam2.son[r][i]) dfs(pam1.son[l][i],pam2.son[r][i]);
}
|
求两字符串的相等回文子串对数
同上题，搜索中将对应节点的 $cnt$ 相乘并求和即可
大写字母蚌埠住了
1
2
3
4
| void dfs(int l,int r){
if(l+r>2) ans+=(ll) pam1.cnt[l]*pam2.cnt[r];
for(rei i=0;i<26;++i) if(pam1.son[l][i] && pam2.son[r][i]) dfs(pam1.son[l][i],pam2.son[r][i]);
}
|