BZOJ2084[Poi2010]Antisymmetry——回文自动机-白红宇的个人博客

BZOJ2084[Poi2010]Antisymmetry——回文自动机

发布日期：2021-08-27 14:53:53 浏览次数：2 分类：技术文章

本文共 1557 字，大约阅读时间需要 5 分钟。

题目描述

对于一个01字符串，如果将这个字符串0和1取反后，再将整个串反过来和原串一样，就称作“反对称”字符串。比如00001111和010101就是反对称的，1001就不是。

现在给出一个长度为N的01字符串，求它有多少个子串是反对称的。

输入

第一行一个正整数N (N <= 500,000)。第二行一个长度为N的01字符串。

输出

一个正整数，表示反对称子串的个数。

样例输入

11001011

样例输出

hint

7个反对称子串分别是：01(出现两次), 10(出现两次), 0101, 1100和001011

对于一个回文串我们判定的方法是对称的位置字符相同，而反对称串则是要求对称的位置字符不同，所以在建回文自动机跳$fail$时只要将判断条件改一下即可。因为反对称串长度一定是偶数，所以不必建出奇回文树(当跳到$1$时就停止)。剩下的就是查询子串数了，一个点所代表的反对称串被所有$fail$指针直接或间接指向它的点所代表的反对称串包含，所以只需要求每个点在$fail$树上的子树权值和即可(因为回文自动机上每个点所代表的的回文串在原串中不一定出现一次，所以每个点的权值不同)。

#include
      
       #include
       #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 #define ll long longusing namespace std;char s[500010];int fail[500010];int tr[500010][26];int len[500010];int n,p,q;int last;int cnt[500010];int num;ll ans;int build(int x){ len[++num]=x; return num;}int main(){ scanf("%d",&n); scanf("%s",s+1); fail[0]=1,len[1]=-1,num=1; for(int i=1;i<=n;i++) { int x=s[i]-'a'; p=last; while((s[i-len[p]-1]==s[i]||i-len[p]-1==0)&&p!=1) { p=fail[p]; } if(s[i-len[p]-1]==s[i]||i-len[p]-1==0) { last=0; continue; } if(!tr[p][x]) { q=build(len[p]+2); int np; np=fail[p]; while((s[i-len[np]-1]==s[i]||i-len[np]-1==0)&&np!=1) { np=fail[np]; } if(s[i-len[np]-1]==s[i]||i-len[np]-1==0) { fail[q]=0; } else { fail[q]=tr[np][x]; } tr[p][x]=q; } cnt[last=tr[p][x]]++; } for(int i=num;i>=1;i--) { cnt[fail[i]]+=cnt[i]; ans+=1ll*cnt[i]; } printf("%lld",ans);}

转载于:https://www.cnblogs.com/Khada-Jhin/p/10418027.html

转载地址：https://blog.csdn.net/weixin_33918357/article/details/92658691 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！

上一篇：2015年终总结

下一篇：BZOJ2863[SHOI2012]魔法树——树链剖分+线段树

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

题目描述

输入

输出

样例输入

样例输出

发表评论

最新留言

关于作者

推荐文章