「OI之路」06字符串-2回文算法

Manacher与回文自动机pam
其实pam比sam好学,可惜没有后者的应用广泛,建议胸怀大痣的同学先学这个

单个字符串、一棵trie的本质不同回文串都是线性的
证明:末端加入一个字符,最多增加一个本质不同回文串,更小的在前面对称那一端一定出现了
可见回文这个特性非常有趣,所以研究相关问题的时候要时刻考虑这一点

Manacher

复杂度证明自己思考一下即可
再次可见本质不同回文串数量也是线性的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
char s2[MAXN*2];
char s[MAXN*2];
int ma[MAXN*2];
int manacher()
{
int ln=strlen(s2+1);
for(int i=1;i<=ln;i++) s[2*i-1]=SPC,s[2*i]=s2[i];
ln=ln*2+1;s[ln]=SPC;

int md,rx=0,ans=0;
for(int i=1;i<=ln;i++)
{
if(i<=rx) ma[i]=min(ma[2*md-1],rx-i+1);
else ma[i]=1;

while(i-ma[i]>=1 and i+ma[i]<=ln and s[i-ma[i]]==s[i+ma[i]]) ma[i]++;
if(rx<i+ma[i]-1) rx=i+ma[i]-1,md=i;
chmax(ans,ma[i]-1);
}
return ans;
}

例题:
[国家集训队]拉拉队排练、[国家集训队]最长双回文串

回文自动机

和回文树是指同一个东西
比较新的玩意,2015发表的

目标:参考sam,线性时空(这里等会具体说明)内构造出一个能接收所有回文子串的自动机
考虑到本质不同的回文子串是线性的(manacher复杂度),所以不用像sam一样用right集合来压缩,直接本质相同的放在一个节点就好了
然后也同样应当由两部分构成:dag、fail树
dag的话因为回文串的特性,加字符应当同时在两边加,所以长度不变应该有奇偶两个dag
fail树的话自然类似地,定义为最长回文后缀
于是初始状态为「0奇ln-1;1偶ln0;fail[1]=0」
另外,细心的读者可能发现了,这个图其实一定是两棵树而不仅仅是dag,因为我们不再需要压缩节点

考虑如何构造,类似sam使用增量法,然后你会发现好写很多
见图:
lst在sam上就是整个串节点,这是因为sam能识别所有子串,而在pam中lst表示最长回文后缀
找到lst后缀链上合适的点,如果没孩子就新建,然后考虑fail是什么就好了
还有就是以当前位置结尾的更短的回文串不需要新建节点,原因也见图

复杂度的话就势能分析,和sam一样的
方案也是sam一样有两种,字符集小就是时间n空间nz,大就是时间nlog空间n

例题:[APIO2014]回文串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
struct PAM
{
char str[N];

int id,lst;struct Nod{int len,fail,cnt,son[26];}p[N];
int node(int ln){p[++id].len=ln;return id;}
PAM(){id=-1;node(-1);node(0);}
int gg(int pp,int pos){while(pp>0 and str[pos-1-p[pp].len]!=str[pos]) pp=p[pp].fail;return pp;}
void insert(int pos,int c)
{
int pp=gg(lst,pos);
if(!p[pp].son[c]) p[ p[pp].son[c]=node(p[pp].len+2) ].fail=(pp?p[ gg(p[pp].fail,pos) ].son[c]:1);
p[lst=p[pp].son[c]].cnt++;//有则节点合并
}
void solve()
{
scanf("%s",str+1);int n=strlen(str+1);
for(int i=1;i<=n;i++) insert(i,str[i]-'a');
ll ans=0;for(int i=id;i>=0;i--) p[p[i].fail].cnt+=p[i].cnt,ans=max(ans,(ll)p[i].cnt*p[i].len);
write(ans);
}
}pam;

还没看懂的话就看这个
以及2017wwt的论文
小结论:一个串的子串的回文自动机是这个串的回文自动机的子图

进阶前置:不基于势能分析的构造法
上述算法的瓶颈在于gg函数,也就是找到一个节点对应字符串中,一个最长的跟在c后面的回文后缀
考虑优化这个过程,发现 只要不是本身 就可以保存下来(因为本身前面会变啊),设为link[c]
转移的话,自己思考一下就会发现,只需要考虑比fail多出来的唯一一个回文后缀————fail本身就好了
那么小字符集的话时空都是n乘字符集,大的话用个可持久化数组就好了,时空 O(nlog字符集)

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
struct PAM
{
char str[N];

int id,lst;struct Nod{int son[26],link[26],fail,len,cnt;}p[N];
int node(int len){p[++id].len=len;return id;}
PAM(){id=-1;node(-1);node(0);}
int gg(int pp,int pos){return (str[pos-1-p[pp].len]==str[pos])?pp:p[pp].link[str[pos]-'a'];}
void insert(int pos,int c)
{
int pp=gg(lst,pos);
if(!p[pp].son[c])
{
int now=node(p[pp].len+2);p[pp].son[c]=now;
int ff=p[now].fail=(pp?p[gg(p[pp].fail,pos)].son[c]:1);
memcpy(p[now].link,p[ff].link,sizeof p[now].link);
p[now].link[str[pos-p[ff].len]-'a']=ff;
}
p[lst=p[pp].son[c]].cnt++;
}
void solve()
{
scanf("%s",str+1);int n=strlen(str+1);
for(int i=1;i<=n;i++) insert(i,str[i]-'a');
ll ans=0;for(int i=id;i>=0;i--) p[p[i].fail].cnt+=p[i].cnt,ans=max(ans,(ll)p[i].cnt*p[i].len);
write(ans);
}
}pam;

还有一种构造法,考虑border的理论
对于每个长度至少3的等差数列,公差d是第三个项的最小周期,然后画一画发现前面的每个d都是相同的
那么找fail的地方依次处理那log个等差数列;节点只需要记录所在等差数列的公差和首项fail
这个方法与字符集大小无关,非常适合大字符集

进阶1:支持前、后端插入、删除的回文树
先考虑前端插入,因为一个节点的最长回文前缀和最长回文后缀都指向一个节点,所以指针一个即可
那么就是在lst外记录一个pre,但要注意前面(后面)插入时会影响到lst(pre),特判即可
例题为 HDU5421 Victor and String 或者 loj141回文子串,code
然后考虑一下后端删除,一开始我很天真地以为,当时怎么加怎么还原不就好了,复杂度肯定一样啊
但其实,因为他是一个均摊复杂度的东西,所以如果能删除我是可以多次重复一个极高复杂度的操作的
于是必须用不基于势能分析的构造法
定义重要子串:对于左端点是最长回文前缀、对于右端点是最长回文后缀
剩下的大概是考虑每个节点,被其他节点压制(使无法重要)的次数,以及有多少个fail指向这里,然后处理删除操作
因为没看到什么题,所以先口胡着吧

进阶2:广义
先考虑字符串集合,和sam一样每次lst设为0,复杂度也同样是长度和
如果要在trie上建回文树,必须用不基于势能分析的,否则复杂度最坏会达到叶子节点深度之和,这个比较显然
例题:Tree Palindromes

pam例题

超详细pam题单

GDKOI2013 D2T4 大山王国的城市规划
这题需要用到一个小定理,回文子串A是B的子串,则要么A=B,要么A是B回文后缀的子串,要么是B删除左右两端后的子串
这个证明其实蛮显然的……就是想的时候有点脑残……因为第三种情况,如果B现在不是A的前、后缀,直接删除B两端就好了
知道这个定理后,dag搞出来,就是最长反链了

CERC2014 Virus synthesis bzoj4044
和上题类似,仔细思考发现并不需要建dag,考虑转移树和fail树
每轮搞完,一定是一个偶回文串左右两边其他字符,那么对回文串dp
若当前为奇回文串,那么可以直接从转移树+2
若当前为偶回文串,则转移树父亲也是偶,其最后一步一定是翻转,则+1(包含了不是前后缀的j);
剩下只需要考虑是前后缀的j,则只需要在fail树上倍增找到ln<=now/2的
f(x)表示恰好在节点x的step,g(x)表示fail树上x到根路径上min step-ln,ans<-now+g(k)

Palindromeness codechef PALPROB
log的做法比较sb,介绍一个线性的,维护half指针,然后从父亲那里暴力向下跳,可以势能分析

「2017 山东一轮集训 Day4」基因 bzoj4932 loj6070
开根号个pam,表示分块后每个位置向右到末尾的pam,每个节点存右端点min,整个pam再开个有序数组存rmin
然后每次询问先lower_bound,然后向左添加字符,判断是否新产生回文串(同样分析后可知最多一个)
时间复杂度为 $O(n \sqrt n)$

有趣的字符串题 湖南省队集训Day2 bzoj5384
数据满足字符串只包含小写字母
和上题不同在于允许离线
考虑border的理论 (感觉border的题目一定要多画图)
那么对于每个等差数列考虑,发现刚好抵消掉,只有两个地方需要修改:

于是维护好等差数列头,枚举每个等差数列在树状数组上搞, $O(nlog^2n)$

Three Palindromes HDU5340
这种题属于n^2艹正解的题,一开始居然还tle,目前是wa……本机拍不出,欢迎指点……
就是用到双回文串的结论,可以看套路集锦,然后偷懒用manacher判断,时间复杂度为 $O(n \sum)$

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
const int N=4e4+10;

char str[N];
namespace PAM
{
int id,lst[2];struct Nod{int son[27],fail,len;}p[N];
int node(int len){p[++id].len=len;return id;}
void clear(){memset(p,0,sizeof p);id=-1;node(-1);node(0);lst[0]=lst[1]=0;}
int gg(int pp,int pos,int op){while(str[pos+(op==1?(-1-p[pp].len):(1+p[pp].len))]!=str[pos])pp=p[pp].fail;return pp;}
void insert(int pos,int c,int op)
{
int pp=gg(lst[op],pos,op);
if(!p[pp].son[c])
{
int now=node(p[pp].len+2);p[pp].son[c]=now;
p[now].fail=(pp?p[gg(p[pp].fail,pos,op)].son[c]:1);
if(p[now].len==pos) lst[op^1]=now;
}
lst[op]=p[pp].son[c];
}
};
int ma[N];char tmp[N];
bool isp(int l,int r)
{
if((r-l+1)%2==0 or (l==r and l&1) or l>r) return 0;
return 2*ma[(l+r)/2]-1>=r-l+1;
}
bool check()
{
scanf("%s",tmp+1);int n=strlen(tmp+1);if(n<3) return 0;
int m=2*n+1;for(int i=1;i<=m;i++) str[i]=(i&1)?('z'+1):tmp[i/2];
ma[1]=1;
for(int md=1,i=2;i<=m;i++)
{
int rmx=md+ma[md]-1;
if(i<=rmx) ma[i]=min(ma[2*i-md],rmx-i+1); else ma[i]=0;
while(i-ma[i]>=1 and i+ma[i]<=m and str[i-ma[i]]==str[i+ma[i]]) ma[i]++;
if(i+ma[i]-1>rmx) md=i;
}
using namespace PAM;clear();
for(int i=1;i<m;i++)
{
insert(i,str[i]-'a',1);
if(isp(i+1,m) and (
( isp(p[lst[0]].len+1,i) and p[lst[0]].len>1 ) or
( isp(1,i-p[lst[1]].len) and p[lst[1]].len>1) )
) return 1;
}
return 0;
}
void main()
{
int T=qread();
while(T--) puts(check()?"Yes":"No");
}

还有两道有空看的题:CF932G、CF722F

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/2435.html
转载请注明出处,谢谢!