【51nod1600】Simple KMP（SAM）（LCT）（差分）

本文主要是介绍【51nod1600】Simple KMP（SAM）（LCT）（差分），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：

对于一个字符串 $∣ S ∣$ ，我们定义 $f a i l [i]$ ，表示最大的 x 使得 $S [1 . . x] = S [i - x + 1 . . i]$ ，满足 $(x < i)$
显然对于一个字符串，如果我们将每个 $0 < = i < = ∣ S ∣$ 看成一个结点，除了 $i = 0$ 以外 $i$ 向 $f a i l [i]$ 连边，这是一颗树的形状，根是 0
我们定义这棵树是 $G (S)$ ，设 $f (S)$ 是 $G (S)$ 中除了 0 号点以外所有点的深度之和
其中 0 号点的深度为 -1
定义 $k e y (S)$ 等于 $S$ 的所有非空子串 $S^{'}$ 的 $f (S^{'})$ 之和
给定一个字符串S，现在你要实现以下几种操作：
1.在 $S$ 最后面加一个字符
2.询问 $k e y (S)$

好题！
考虑新加一个字符的贡献，就是考虑所有的后缀的新增贡献

注意到，某一个后缀的新增贡献，就是它往上跳一个 $f a i l$ ，然后剩下的就全部是跳上去过后的那个点的贡献，而这个点在之前作为后缀出现过，所以我们只需要算出一个增量的差分数组

每一个后缀的新增贡献是它在 $G (S)$ 中的深度
注意到统计一棵树的深度和可以等价于统计每个点的 $s i z e$ 和
也就是这个套路
$\sum_ii*\sum_{dep=i}1=\sum_i\sum_{dep\ge i}1$
又注意到这个就等价于对每一个后缀统计它的贡献，需要算它出现了多少次
就是把 $f a i l$ 链提出来，对每个点的贡献就是 $(l e n [x] - l e n [f a [x]]) * s i z [x]$
需要支持换父亲，链加， $L C T$ 即可
感觉差分，从上一步走来，就像是站在巨人的肩膀上

#include<bits/stdc++.h>
#define cs const
using namespace std;
cs int N = 2e5 + 5;
cs int Mod = 1e9+7;
typedef long long ll;
int add(int a, int b){ return a+b>=Mod?a+b-Mod:a+b; }
int mul(int a, int b){ return (ll)a*b%Mod; }
void Add(int &a, int b){ a = add(a, b); }
int n; char s[N];
namespace LCT{int ch[N][2], fa[N], r[N], tg[N], len[N], sm[N], vl[N];bool isr(int x){ return ch[fa[x]][0] != x && ch[fa[x]][1] != x; }int get(int x){ return ch[fa[x]][1] == x; }void pushup(int x){sm[x]=sm[ch[x][0]]+len[x]+sm[ch[x][1]];vl[x]=add(add(vl[ch[x][0]],vl[ch[x][1]]),mul(r[x],len[x]));}void tag(int x, int v){ if(!x) return; Add(r[x],v); Add(tg[x],v); Add(vl[x],mul(sm[x],v)); }void down(int x){ if(tg[x]) tag(ch[x][0],tg[x]), tag(ch[x][1],tg[x]),tg[x]=0; }void path(int x){ if(!isr(x)) path(fa[x]); down(x); }void rot(int x){int y=fa[x],z=fa[y],k=get(x); if(!isr(y)) ch[z][get(y)]=x; fa[x]=z;ch[y][k]=ch[x][k^1]; fa[ch[x][k^1]]=y; ch[x][k^1]=y; fa[y]=x; pushup(y); pushup(x);}void spl(int x){ path(x); while(!isr(x)){ int y=fa[x]; if(!isr(y)) rot(get(x)^get(y)?x:y); rot(x); } }void acs(int x){ for(int y=0;x;y=x,x=fa[x]) spl(x),ch[x][1]=y,pushup(x); }void link(int x, int y){ acs(x); spl(x); fa[x] = y; }void cut(int x, int y){ acs(x); spl(x); spl(y); ch[y][1]=fa[x]=0; pushup(y); }
}
namespace SAM{int ch[N][26], lk[N], r[N], len[N], las=1, node=1;void init(int x){LCT::len[x]=len[x]-len[lk[x]];LCT::r[x]=r[x]; LCT::pushup(x);}int extend(int c){int now = ++node, p = las; len[now]=len[p]+1; r[now]=1;for(;p&&!ch[p][c];p=lk[p]) ch[p][c]=now;if(!p) lk[now]=1, init(now), LCT::link(now,1);else{int q = ch[p][c]; if(len[q]==len[p]+1) lk[now]=q, init(now), LCT::link(now,q);else{int cl = ++node; len[cl]=len[p]+1; lk[cl]=lk[q]; memcpy(ch[cl],ch[q],sizeof(ch[q]));LCT::acs(q); LCT::spl(q);r[cl]=r[q]=LCT::r[q];init(cl);LCT::link(cl,lk[cl]);LCT::cut(q,lk[q]);lk[now]=lk[q]=cl;init(q); init(now);LCT::link(now,lk[now]);LCT::link(q,lk[q]);for(;p&&ch[p][c]==q;p=lk[p]) ch[p][c]=cl;}} las = now;LCT::acs(now); LCT::spl(now); int ps=LCT::ch[now][0], delta=LCT::vl[ps]; LCT::tag(ps,1); return delta;}
}
int main(){scanf("%s",s+1); n=strlen(s+1);int res = 0, ans = 0;for(int i = 1; i <= n; i++){Add(res, SAM::extend(s[i]-'a'));Add(ans, res); cout << ans << '\n';} return 0;
}