P4248 [AHOI2013]差异

蔚落 2021-12-23 13:59 226阅读 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 条评论，226人围观）

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

相关阅读

相关【LCA】P4281 [AHOI2008]紧急集合 / 聚会

[P4281 \[AHOI2008\]紧急集合 / 聚会 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)][P4281 _AHOI2008_ _ _ - _

客官°小女子只卖身不卖艺/ 2024年03月16日 09:39/ 0 赞/ 17 阅读

相关洛谷——P2550 [AHOI2001]彩票摇奖

P2550 \[AHOI2001\]彩票摇奖题目描述为了丰富人民群众的生活、支持某些社会公益事业，北塔市设置了一项彩票。该彩票的规则是： 1. 每张彩票上印

àì夳堔傛蜴生んèń/ 2023年10月02日 13:46/ 0 赞/ 17 阅读

相关 AHOI2018 排列

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

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

相关洛谷-P2550 [AHOI2001]彩票摇奖

题目描述为了丰富人民群众的生活、支持某些社会公益事业，北塔市设置了一项彩票。该彩票的规则是： (1) 每张彩票上印有 7 个各不相同的号码，且这些号码的取指范围为 1

柔光的暖阳◎/ 2023年05月30日 15:54/ 0 赞/ 26 阅读

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

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

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

相关 P4248 [AHOI2013]差异

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

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

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

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

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

相关 P4098 [HEOI2013]ALO

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

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

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

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

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

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

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

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