HDU 5421 Victor and String (回文自动机)

题目大意：让你维护一个字符串，支持在开头结尾插入字符，以及查询本质不同的回文串数量以及回文串总数量

开头结尾都维护一个$last$指针，如果插入新字符后，整个串是一个回文串，就把另一个$last$赋值成当前的$last$

为什么这样做就是正确的呢？

首先，对于这道题而言，一个回文串开头/结尾是等价的

不合并$last$的情况下，在当前方向添加字符不会被另一个方向所影响，就相当于只在末尾加字符

如果合并了$last$，说明现在另一个方向的开头字符，能和新添加的字符共同产生贡献，所以必须把另一个$last$赋值成当前的$last$，来完成都是在末尾新添加字符的“假象”

本质不同的回文串数量就是节点个数，回文串总数量就是所有节点在$pre$树中的深度总和*作为回文末尾的次数

每次$insert$时都更新即可，注意开$longlong$

 #include <cmath>

 #include <vector>

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #define N1 200100

 #define S1 (N1<<1)

 #define ll long long

 #define uint unsigned int

 #define rint register int

 #define dd double

 #define il inline

 #define inf 0x3f3f3f3f

 #define idx(X) (X-'a')

 using namespace std;

 int gint()

 {

     int ret=,fh=;char c=getchar();

     while(c<''||c>''){if(c=='-')fh=-;c=getchar();}

     while(c>=''&&c<=''){ret=ret*+c-'';c=getchar();}

     return ret*fh;

 }

 int n,L,R;

 namespace PAM{

 int trs[N1][],pre[N1],dep[N1],num[N1];

 int lla,rla,tot;ll sum;

 void init(){tot=lla=rla=,dep[]=-,pre[]=pre[]=;}

 int lchk(char *str,int i,int p){return str[i+dep[p]+]!=str[i]?:;}

 int rchk(char *str,int i,int p){return str[i-dep[p]-]!=str[i]?:;}

 void Lins(char *str,int i)

 {

     int p=lla,np,fp,c=idx(str[i]);

     while(lchk(str,i,p)) p=pre[p];

     if(!trs[p][c])

     {

         np=++tot;

         dep[np]=dep[p]+;

         fp=pre[p];

         while(lchk(str,i,fp)) fp=pre[fp];

         pre[np]=trs[fp][c];

         trs[p][c]=np;

         num[np]=num[pre[np]]+;

     }

     lla=trs[p][c];

     if(dep[trs[p][c]]==R-L+) rla=lla;

     sum+=num[lla];

 }

 void Rins(char *str,int i)

 {

     int p=rla,np,fp,c=idx(str[i]);

     while(rchk(str,i,p)) p=pre[p];

     if(!trs[p][c])

     {

         np=++tot;

         dep[np]=dep[p]+;

         fp=pre[p];

         while(rchk(str,i,fp)) fp=pre[fp];

         pre[np]=trs[fp][c];

         trs[p][c]=np;

         num[np]=num[pre[np]]+;

     }

     rla=trs[p][c];

     if(dep[trs[p][c]]==R-L+) lla=rla;

     sum+=num[rla];

 }

 void clr()

 {

     tot++;

     memset(trs,,tot**);

     memset(pre,,tot*);

     memset(dep,,tot*);

     memset(num,,tot*);

     tot=lla=rla=;sum=;

 }

 };

 char str[N1];

 int main()

 {

     //freopen("t2.in","r",stdin);

     //freopen("a.out","w",stdout);

     while(scanf("%d",&n)!=EOF)

     {

         int fl;L=,R=;

         char tmp[];

         PAM::clr(),PAM::init();

         memset(str,,sizeof(str));

         while(n--)

         {

             scanf("%d",&fl);

             if(fl==){

                 scanf("%s",tmp);

                 str[--L]=tmp[];

                 PAM::Lins(str,L);

             }else if(fl==){

                 scanf("%s",tmp);

                 str[++R]=tmp[];

                 PAM::Rins(str,R);

             }else if(fl==){

                 printf("%d\n",PAM::tot-);

             }else if(fl==){

                 printf("%lld\n",PAM::sum);

             }

         }

     }

     return ;

 }

巴特西

HDU 5421 Victor and String (回文自动机)

最新文章

热门文章