P4248 [AHOI2013]差异

蔚落 2021-12-23 13:59 212阅读 0赞

### 思路 ###

SAM  
后缀自动机parent树的LCA就是两个子串的最长公共后缀  
现在要求LCP  
所以把字符串反转一下  
然后每个点的贡献就是endpos的大小，dfs一遍求出贡献就可以了

### 代码 ###

#include <cstdio> #include <algorithm> #include <cstring> #define int long long using namespace std; const int MAXN = 500500*2; int Nodecnt,trans[MAXN][26],suflink[MAXN],endpos[MAXN],maxlen[MAXN],fir[MAXN],nxt[MAXN],v[MAXN],cnt,ans,n; char s[MAXN]; int sum(int l,int r){ if(r<l) return 0; return (r+l)*(r-l+1)/2; } void addedge(int ui,int vi){ ++cnt; v[cnt]=vi; nxt[cnt]=fir[ui]; fir[ui]=cnt; } int New_state(int _maxlen,int *_trans,int _suflink){ int o=++Nodecnt; maxlen[o]=_maxlen; suflink[o]=_suflink; if(_trans){ for(int i=0;i<26;i++) trans[o][i]=_trans[i]; } return o; } int add_len(int u,int c){ int z=New_state(maxlen[u]+1,NULL,0); endpos[z]=1; while(u&&(trans[u][c]==0)){ trans[u][c]=z; u=suflink[u]; } if(!u){ suflink[z]=1; return z; } int v=trans[u][c]; if(maxlen[u]+1==maxlen[v]){ suflink[z]=v; return z; } int y=New_state(maxlen[u]+1,trans[v],suflink[v]); suflink[z]=suflink[v]=y; while(u&&trans[u][c]==v){ trans[u][c]=y; u=suflink[u]; } return z; } void dfs(int x){ for(int i=fir[x];i;i=nxt[i]){ dfs(v[i]); ans-=endpos[v[i]]*endpos[x]*maxlen[x]*2; endpos[x]+=endpos[v[i]]; } } signed main(){ scanf("%s",s+1); n=strlen(s+1); reverse(s+1,s+n+1); Nodecnt=1; int last=1; for(int i=1;i<=n;i++) last=add_len(last,s[i]-'a'); for(int i=1;i<=n;i++){ int j=i+1; ans+=(n-i+1)*(n-j+1)+sum(1,n-j+1); } for(int i=2;i<=Nodecnt;i++) addedge(suflink[i],i); dfs(1); printf("%lld\n",ans); return 0; }

转载于:https://www.cnblogs.com/dreagonm/p/10634414.html

发表评论取消回复

表情：

评论列表（有 0 条评论，212人围观）

还没有评论，来说两句吧...

相关阅读

相关 AHOI2018 排列

首先是那个非常吃shi的题意，想好久一会就能发现题里面的意思是：　　如果某一个数的值为x，那么它必须排在第x个数后面。　　然后我们就可以发现形成了一棵树，第i个数的父亲

ゞ浴缸里的玫瑰/ 2023年08月17日 16:48/ 0 赞/ 82 阅读

相关 P1981 [NOIP2013 普及组] 表达式求值

[P1981 \[NOIP2013 普及组\] 表达式求值][P1981 _NOIP2013 _] 题目描述给定一个只包含加法和乘法的算术表达式，请你编程计算表达式

落日映苍穹つ/ 2023年01月13日 09:34/ 0 赞/ 279 阅读

相关洛谷P1403 [AHOI2005]约数研究

题目描述科学家们在Samuel星球上的探险得到了丰富的能源储备，这使得空间站中大型计算机“Samuel II”的长时间运算成为了可能。由于在去年一年的辛苦工作取得了不错

男娘i/ 2022年05月30日 11:27/ 0 赞/ 153 阅读

相关 Luogu P4097 [HEOI2013]Segment 李超线段树

[题目链接 \\(Click\\) \\(Here\\)][_Click_ _Here] 李超线段树的模板。但是因为我实在太\\(Naive\\)了，想象不到实现方法。

墨蓝/ 2022年01月09日 10:49/ 0 赞/ 198 阅读

相关 P4248 [AHOI2013]差异

思路 SAM 后缀自动机parent树的LCA就是两个子串的最长公共后缀现在要求LCP 所以把字符串反转一下然后每个点的贡献就是endpos的大小，d

蔚落/ 2021年12月23日 13:59/ 0 赞/ 212 阅读

相关 BZOJ 3238 [Ahoi2013]差异 ——后缀自动机

后缀自动机的parent树就是反串的后缀树。所以只需要反向构建出后缀树，就可以乱搞了。 include <cstdio> include <cstring

柔情只为你懂/ 2021年12月21日 05:05/ 0 赞/ 240 阅读

相关「AHOI / HNOI2017」单旋

「AHOI / HNOI2017」单旋 [题目链接][Link 1] H 国是一个热爱写代码的国家，那里的人们很小去学校学习写各种各样的数据结构。伸展树（splay）是

浅浅的花香味﹌/ 2021年12月20日 10:17/ 0 赞/ 176 阅读

相关 P4098 [HEOI2013]ALO

[题意分析][Link 1] 题目链接这里借鉴了\\(Youngsc\\)以及\\(hzwer\\)的思路首先由于涉及到了区间异或最值的问题所以我们需要使

野性酷女/ 2021年12月20日 07:33/ 0 赞/ 154 阅读

相关洛谷 P2051 [AHOI2009]中国象棋

题目描述这次小可可想解决的难题和中国象棋有关，在一个N行M列的棋盘上，让你放若干个炮（可以是0个），使得没有一个炮可以攻击到另一个炮，请问有多少种放置方法。大家肯定很清

心已赠人/ 2021年11月22日 08:12/ 0 赞/ 288 阅读

相关洛谷——P2559 [AHOI2002]哈利·波特与魔法石

P2559 \[AHOI2002\]哈利·波特与魔法石题目描述 ![1681.png][] 输入输出格式输入格式：文件中第一行有七个数，

墨蓝/ 2021年09月20日 07:12/ 0 赞/ 267 阅读