【学习笔记】回文自动机
-
定义：
- 一种用来存储一个串的所有回文子串的结构；
- 本质是两颗trie，每个节点存储回文子串的一半，用来代表整个回文串；
- 两颗是由于回文串长度有奇偶，所以需要奇数节点根和偶数节点根；
- 每个节点的fail指针表示节点对应回文子串的最大回文后缀节点；
- 也就是说，x->y说明了y所代表的回文串是x所代表的回文串在回文自动机里出现过的最大后缀；
- ch[i][]存储trie树,len[i]表示i号节点代表的回文串的长度；
-
例子：
- 以”aabbcbbc”为例：
-
-
算法：
- 在线算法，不断加入末尾的字符串；
- 假设加入到第i位，设置一个last记录最后i-1位的最大回文后缀节点；
- 如果s[j]..s[i]是一个回文串，那么s[j+1]…s[i-1]也是一个回文串，可以考虑由i-1的回文后缀转移;
- 沿着last的fail边不断向上找到第一个形成新的i的回文串的节点now( 只需要满足：s[ i – len[now] – 1]==s[i] )；
- 如果now的儿子里有字符s[i]的对应边，那么对应儿子就是第i位的最大回文后缀节点；
- 否则新建now的一个对应儿子new(len[new]=len[now]+2)，这就是第i位的最大回文后缀节点；
- 还需要为新建点new设置fail边，根据回文串的对称性并且new节点的回文串包含了fl[new]；
- 那么fl[new]对应的回文串一定在前面(1..i-1的位置)出现过，所以不会再新建fl[new]，找到直接连即可，这保证了复杂度；
- 唯一一种情况比较特殊就是new==1，此时为new找fail的时候可能找到new自己；
- 将奇数节点标号为1，偶数节点标号为0，所有节点的儿子初始为0，先设置fl[new]再和now连边可以避免麻烦;
- 有时需要记录cnt[]表示一个节点对应的回文后缀的个数；
-
1 int n,sz,ch[N][26],fl[N],cnt[N],len[N],now; 2 char s[N]; 3 ----------------------------------------------------------------------- 4 int find(int x,int y){return s[y]==s[y-len[x]-1]?x:find(fl[x],y);} 5 ----------------------------------------------------------------------- 6 fl[0]=1; fl[sz=1]=1; 7 len[0]=0; len[1]=-1; 8 now=0; 9 for(int i=0,c;s[i];i++){ 10 now=find(now,i); 11 if(!ch[now][c=s[i]-\'a\']){ 12 fl[++sz]=ch[find(fl[now],i)][c]; 13 len[ch[now][c]=sz]=len[now]+2; 14 } 15 cnt[now=ch[now][c]]++; 16 }
-
性质：
-
1.匹配
- 回文自动机存储了所有本质不同的回文子串，所以只要不断u=ch[u][s[i]-\’a\’]就可以判断s是否是某个串的一个回文子串；
- 和ac自动机的匹配类似，找到到一个节点代表着沿着fail边的所有节点都被找到了；
-
2.fail树
- 和ac自动机的fail树类似，fail边会形成一个树的结构，向上走可以找到当前节点的所有后缀节点；
- 所以通过cnt[]的递推可以统计回文子串的个数；即：$(cnt[fl[i]]+=cnt[i])$；
-
-
习题：
- bzoj2565最长双回文串
- 用回文自动机正反两边跑出每个点的前后最长回文串，枚举断点统记ans
-
1 #include<bits/stdc++.h> 2 #define rg register 3 #define il inline 4 using namespace std; 5 const int N=100010; 6 char s[N]; 7 int n,sz,fl[N],len[N],ch[N][26],l[N],r[N]; 8 il int find(int x,int y){ 9 return s[y]==s[y-len[x]-1]?x:find(fl[x],y); 10 } 11 void cal(){ 12 memset(ch,0,sizeof(ch)); 13 memset(fl,0,sizeof(fl)); 14 sz=1; 15 fl[0]=1;fl[1]=1; 16 len[0]=0;len[1]=-1; 17 for(rg int i=1,now;i<=n;i++){ 18 now = find(now,i); 19 if(!ch[now][s[i]-\'a\']){ 20 len[++sz]=len[now]+2; 21 fl[sz]=ch[find(fl[now],i)][s[i]-\'a\']; 22 ch[now][s[i]-\'a\']=sz; 23 } 24 now=ch[now][s[i]-\'a\']; 25 r[i] = len[now]; 26 } 27 } 28 int main(){ 29 freopen("bzoj2565.in","r",stdin); 30 freopen("bzoj2565.out","w",stdout); 31 s[0] = -1; 32 scanf("%s",s+1); 33 n=strlen(s+1); 34 cal(); 35 for(rg int i=1;i<=n;i++)l[i] = r[i]; 36 for(rg int i=1;i<=n>>1;i++) 37 swap(s[i],s[n-i+1]); 38 cal(); 39 int ans = 0; 40 for(rg int i=1;i<n;i++){ 41 ans = max(ans, l[i] + r[n - i]); 42 } 43 cout << ans << endl; 44 return 0; 45 }
bzoj2565
- bzoj3676[Apio2014]回文串
- 回文自动机里节点保存状态是本质不同的回文串；
-
记录每个节点更新的次数$cnt[]$ , 一个节点出现同时代表其fail祖先都出现，所以$cnt[ fl[i] ] += cnt[i]$;
-
有个技巧：回文自动机的拓扑序即编号序列；
1 #include<bits/stdc++.h> 2 #define rg register 3 #define il inline 4 #define Run(i,l,r) for(rg int i=l;i<=r;i++) 5 #define Don(i,l,r) for(rg int i=l;i<=r;i++) 6 #define ll long long 7 using namespace std; 8 const int N=300100; 9 int n,fl[N],ch[N][26],tot,len[N],sz; 10 ll cnt[N]; 11 char s[N]; 12 inline int find(int x,int y){ 13 while(1){ 14 if(s[x - len[y] - 1] == s[ x ])break; 15 y = fl[ y ]; 16 } 17 return y; 18 } 19 int main(){ 20 freopen( "bzoj3676.in" , "r" , stdin); 21 freopen( "bzoj3676.out", "w", stdout); 22 scanf("%s",s+1); 23 sz=1; 24 fl[0]=fl[1]=1; 25 len[0]=0;len[1]=-1; 26 int now = 0 ; 27 s[0] = -1; 28 for(n=1 ; s[ n ] ; n++){ 29 s[ n ] -= \'a\' ; 30 now = find( n , now ); 31 if(! ch[ now ][ s[n] ]){ 32 len[ ++sz ] = len[now] + 2; 33 int tmp = find( n , fl[ now ] ); 34 fl[ sz ] = ch[ tmp ][ s[n] ]; 35 ch[ now ][ s[n] ] = sz ; 36 } 37 cnt[ now = ch[ now ][ s[n] ] ] ++; 38 } 39 ll ans = 0; 40 for( int i = sz; i > 1 ; --i){ 41 cnt[ fl[i] ] += cnt[ i ]; 42 ans = max(ans , cnt[i] * len[i] ); 43 } 44 cout << ans << endl; 45 return 0; 46 }
bzoj3676
- bzoj4480[Jsoi2013]快乐的jyy
- 回文串出现次数的乘积的和的话。。。
- 先对$A$串做回文自动机，然后$hash$存下每个回文串出现次数
- 然后对$B$串再做一次统计答案
-
$hash$注意区分奇偶，同时每位最小值不要出现0 ，$fxy$说常见模数+底$26$是被卡了的($推荐2333333$)
1 #include<cstdio> 2 #include<iostream> 3 #include<map> 4 #include<cstring> 5 #define rg register 6 #define il inline 7 #define ull unsigned long long 8 #define ll long long 9 #define base 233 10 using namespace std; 11 const int N=50010; 12 ull h[N]; 13 char s[N]; 14 ll cnt[N],ans; 15 int n,sz,fl[N],ch[N][26],len[N],db[N]; 16 map<ull,ll>mp; 17 il int newd(int d){ 18 len[sz]=d; 19 fl[sz]=cnt[sz]=h[sz]=0; 20 memset(ch[sz],0,sizeof(ch[sz])); 21 return sz++; 22 } 23 void init(){ 24 s[0]=-1; 25 sz=0; 26 newd(0);newd(-1); 27 fl[0]=fl[1]=1; 28 h[0]=0;h[1]=-1; 29 } 30 il int find(int x,int y){return s[x]==s[x-len[y]-1]?y:find(x,fl[y]);} 31 void solve(int fg){ 32 init(); 33 int l = strlen(s+1); 34 for(rg int i=1,now=0;i<=l;i++){ 35 now = find(i,now); 36 if(!ch[now][s[i]-\'A\']){ 37 fl[newd(len[now]+2)]=ch[find(i,fl[now])][s[i]-\'A\']; 38 ch[now][s[i]-\'A\']=sz-1; 39 h[sz-1]=h[now]*base+s[i]; 40 } 41 now = ch[now][s[i]-\'A\']; 42 cnt[now]++; 43 db[i] = len[now]; 44 } 45 for(rg int i=sz-1;i>=2;i--)if(!fg){ 46 cnt[fl[i]]+=cnt[i]; 47 mp[h[i]] = cnt[i]; 48 }else{ 49 cnt[fl[i]]+=cnt[i]; 50 ans += mp[h[i]] * cnt[i]; 51 } 52 } 53 int main(){ 54 freopen("bzoj4480.in","r",stdin); 55 freopen("bzoj4480.out","w",stdout); 56 scanf("%s",s+1);solve(0); 57 scanf("%s",s+1);solve(1); 58 printf("%lld\n",ans); 59 return 0; 60 }
bzoj4480
版权声明：本文为Paul-Guderian原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。