bzoj 3676 [Apio2014]回文串（Manacher+SAM）

时间：2024-08-03 17:05:44

【题目链接】

http://www.lydsy.com/JudgeOnline/problem.php?id=3676

【题意】

给定一个字符串，定义一个串的权值为长度*出现次数，求最大权的回文子串。

【思路】

马拉车求出本质不同的回文子串。

对于一个回文子串，在SAM中用倍增法在O(logn)的时间得到它的出现次数，即SAM中每个节点的right集大小，倍增数组和right都可以通过提前处理得到。

更新答案即可。

　先来考虑一个简单的问题：

给出一个串S（|S|<=1000000）和M个询问，每次询问S中[si,ti]这一段串在总串中出现过几次。
显然我们可以建出后缀数组并用二分+ST表简单地完成。
但如果我们一定要用后缀自动机的知识呢？
我们会发现，倘若我们能快速找到一个节点（状态）表示当前s~t这一段，只需直接调用它的size即可。
（有关size的预处理：在SAM建立好之后，用所有点的size去累加它的parent的size）
那么如何快速找到这样一个状态呢？
首先SAM有一个性质：把每一个节点向它的parent连边，得到的树是原串的逆序串的后缀树。（只是这棵后缀树压缩后的边权都不知道）
也就是说，如果我们构建出一棵SAM，它将同时有后缀树和trie的性质。
举个例子，比如字符串baabaaa。设询问为s=5，t=6
首先画出对应的后缀树（空节点不再画出）：
bzoj 3676 [Apio2014]回文串（Manacher+SAM）
注意此时后缀树中“浅”的点表示的是“后缀”。
我们先跑出从1开始到t的状态s，此时设我们在SAM中的节点p。样例里p对应在后缀树的最下面那个点。
但是我们发现1~t的状态太长了，我们只需要s~t的状态。
这样我们可以在这棵后缀树上倍增，能往某个祖先跑就往某个祖先跑。能跑的依据就是该祖先的深度>=t-s+1
这样，我们就跑到了p节点在后缀树上的父亲的父亲，然后直接在SAM里调用它的信息即可。
这里还有一个细节问题：如果询问是s=3,t=6，应该返回哪个点呢？
这个时候发现不能完全覆盖，要不一个点少一些，要不一个点多一些。
显然要把剩下的部分也选进去，也就是说仍然在p这个点。合法性显然，且可以证明这样最优。
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　Quote from Here

【代码】

 #include<set>

 #include<cmath>

 #include<queue>

 #include<vector>

 #include<cstdio>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 #define trav(u,i) for(int i=front[u];i;i=e[i].nxt)

 #define FOR(a,b,c) for(int a=(b);a<=(c);a++)

 #define rep(a,b,c) for(int a=(b);a>=(c);a--)

 using namespace std;

 typedef long long ll;

 const int N = 6e5+;

 const int D = ;

 char s[N];

 int n,p[N];

 struct SAM

 {

     ll ans;

     int sz,last,ch[N][],fa[N],R[N],pos[N],l[N],b[N],cnt[N],fat[N][D];

     SAM()

     {

         sz=ans=; last=++sz;

         memset(cnt,,sizeof(cnt));

         memset(R,,sizeof(R));

         memset(fat,,sizeof(fat));

     }

     void add(int c,int id)

     {

         int np=++sz,p=last; last=np;

         l[np]=l[p]+; R[np]=; pos[id]=last;

         for(;p&&!ch[p][c];p=fa[p]) ch[p][c]=np;

         if(!p) fa[np]=;

         else {

             int q=ch[p][c];

             if(l[q]==l[p]+) fa[np]=q;

             else {

                 int nq=++sz; l[nq]=l[p]+;

                 memcpy(ch[nq],ch[q],sizeof(ch[q]));

                 fa[nq]=fa[q];

                 fa[q]=fa[np]=nq;

                 for(;ch[p][c]==q;p=fa[p]) ch[p][c]=nq;

             }

         }

     }

     void get_pre()

     {

         FOR(i,,sz) cnt[l[i]]++;

         FOR(i,,n) cnt[i]+=cnt[i-];

         rep(i,sz,) b[cnt[l[i]]--]=i;

         rep(i,sz,) R[fa[b[i]]]+=R[b[i]];

         FOR(i,,sz) {

             fat[i][]=fa[i];

             FOR(j,,D-)

                 fat[i][j]=fat[fat[i][j-]][j-];

         }

     }

     void get_ans(int u,int v)

     {

         int x=pos[v];

         for(int i=D-;i>=;i--) {

             int t=fat[x][i];

             if(l[t]>=v-u+) x=t;

         }

         ans=max(ans,(ll)R[x]*(v-u+));

     }

 } sam;

 void Manacher()

 {

     int mx=,id;

     for(int i=;i<=n;i++) {

         if(mx>i) p[i]=min(mx-i,p[*id-i-]);

         else p[i]=;

         while(s[i+p[i]+]==s[i-p[i]]) {

             p[i]++;

             sam.get_ans(i-p[i]+,i+p[i]);

         }

         if(p[i]+i>mx) mx=p[i]+i,id=i;

     }

     mx=;

     for(int i=;i<=n;i++) {

         if(mx>i) p[i]=min(mx-i-,p[*id-i]);

         else p[i]=,sam.get_ans(i,i);

         while(s[i+p[i]]==s[i-p[i]]) {

             p[i]++;

             sam.get_ans(i-p[i]+,i+p[i]-);

         }

         if(p[i]+i>mx) mx=p[i]+i,id=i;

     }

 }

 int main()

 {

     scanf("%s",s+);

     n=strlen(s+);

     FOR(i,,n) sam.add(s[i]-'a',i);

     sam.get_pre();

     s[]='+',s[n+]='-';

     Manacher();

     printf("%lld",sam.ans);

     return ;

 }

相关文章