首页 > 代码库 > 【hihocoder#1413】Rikka with String 后缀自动机 + 差分
【hihocoder#1413】Rikka with String 后缀自动机 + 差分
题目链接：http://hihocoder.com/problemset/problem/1413
这个题非常的劲！
首先可以发现，每次只变换一个字符为#，所以每次答案一定会得到相应的包含#的答案，而这个方案是可以直接计算出来的。
假设是$S[i]=$#则会得到$i*(N-i+1)$的子串数。
所以每次的答案可以表示为$sum[root]+i*(N-i+1)-ans[i]$，其中$ans[i]$表示严格经过$i$位置的本质不同的子串，严格的意义即这个本质不同的子串有且仅有一次，且经过$i$；
所以问题就转化为如何求出$ans[1..N]$
然后如何找到本质不同的经过$i$的子串，考虑利用后缀自动机；
问了 abclzr队长 ，可以考虑存出每个$Parent$树中的节点的$Right$集合，这样再进行递推，就可以搞出答案，但实际上并不需要存出全部的$Right$集合，只需要记录每个节点的$Right$集合的最左最右端点。
这样，对于一个子串是否严格跨越$i$，就可以利用右端-距离+1以及左端来判断是否严格跨越。
然后每个节点代表了多个子串，把这些子串一起处理，对答案的贡献就相当于是区间加上一个等差数列，对$ans[]$二阶差分后可以$O(N)$出解。
其实也可以用线段树/树状数组维护，树状数组需要差分，而且构造两个比较好写，线段树只要支持区间加，单点加，区间和即可。
给出一下官方题解：
Code：
#include<iostream>#include<cstdio>#include<cmath>#include<algorithm>#include<cstring>using namespace std;#define LL long long#define MAXN 600010int N;char S[MAXN];namespace SAM{ int son[MAXN<<1][27],par[MAXN<<1],len[MAXN<<1],size[MAXN<<1],l[MAXN<<1],r[MAXN<<1]; int root,last,sz; #define INF 0x7fffffff inline void Init() {root=last=sz=1;} inline void Extend(int c) { int cur=++sz,p=last; len[cur]=len[p]+1; size[cur]=1; while (p && !son[p][c]) son[p][c]=cur,p=par[p]; if (!p) par[cur]=root; else { int q=son[p][c]; if (len[p]+1==len[q]) par[cur]=q; else { int nq=++sz; l[nq]=INF,r[nq]=0; memcpy(son[nq],son[q],sizeof(son[nq])); par[nq]=par[q]; len[nq]=len[p]+1; while (p && son[p][c]==q) son[p][c]=nq,p=par[p]; par[cur]=par[q]=nq; } } l[cur]=r[cur]=len[cur]; last=cur; } inline void Build() {Init(); for (int i=1; i<=N; i++) Extend(S[i]-‘a‘+1);} int st[MAXN],id[MAXN<<1]; LL sum[MAXN<<1],ans[MAXN]; inline void Pre() { for (int i=1; i<=sz; i++) st[len[i]]++; for (int i=1; i<=N; i++) st[i]+=st[i-1]; for (int i=1; i<=sz; i++) id[st[len[i]]--]=i; for (int i=sz; i>=1; i--) { int x=id[i]; l[par[x]]=min(l[par[x]],l[x]); r[par[x]]=max(r[par[x]],r[x]); for (int j=1; j<=26; j++) sum[x]+=sum[son[x][j]]; sum[x]++; } sum[root]--; for (int i=sz; i>=1; i--) { int x=id[i]; if (r[x]-len[x]+1<=l[x]) { int L=r[x]-len[x]+1,R=min(r[x]-len[par[x]],l[x]),Len=R-L+1; if (L<=R) ans[L]++,ans[R+1]-=Len+1,ans[R+2]+=Len; L=R+1,R=l[x]; if (L<=R) ans[L]+=Len,ans[L+1]-=Len,ans[R+1]-=Len,ans[R+2]+=Len; } } for (int i=1; i<=N; i++) ans[i]+=ans[i-1]; for (int i=1; i<=N; i++) ans[i]+=ans[i-1];// printf("%d\n",sum[root]); }}using namespace SAM;int main(){ scanf("%d%s",&N,S+1); SAM::Build(); SAM::Pre(); for (int i=1; i<=N; i++) printf("%lld ",(LL)i*(N-i+1)+sum[root]-ans[i]); return 0;}/*10abcabcabdc*/
【hihocoder#1413】Rikka with String 后缀自动机 + 差分
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。