2020-2021:teams:legal_string:jxm2001:字符串_3
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:legal_string:jxm2001:字符串_3 [2020/08/31 11:33] jxm2001 |
2020-2021:teams:legal_string:jxm2001:字符串_3 [2020/09/02 10:52] (当前版本) jxm2001 |
||
|---|---|---|---|
| 行 1: | 行 1: | ||
| ====== 字符串 3 ====== | ====== 字符串 3 ====== | ||
| - | ===== 后缀数组 ===== | + | ===== 后缀数组(SA) ===== |
| ==== 算法简介 ==== | ==== 算法简介 ==== | ||
| 行 41: | 行 41: | ||
| <code cpp> | <code cpp> | ||
| namespace SA{ | namespace SA{ | ||
| - | int sa[MAXN],rk[MAXN],height[MAXN],x[MAXN],y[MAXN],c[MAXN]; | + | int sa[MAXN],rk[MAXN],height[MAXN],X[MAXN],Y[MAXN],c[MAXN]; |
| int d[MAXN][MAXM],lg2[MAXN]; | int d[MAXN][MAXM],lg2[MAXN]; | ||
| void get_sa(char *s,int n,int m){//s下标从1开始 | void get_sa(char *s,int n,int m){//s下标从1开始 | ||
| + | int *x=X,*y=Y; | ||
| _rep(i,0,m)c[i]=0; | _rep(i,0,m)c[i]=0; | ||
| _rep(i,1,n)c[x[i]=s[i]]++; | _rep(i,1,n)c[x[i]=s[i]]++; | ||
| 行 559: | 行 560: | ||
| enter(ans); | enter(ans); | ||
| } | } | ||
| + | return 0; | ||
| + | } | ||
| + | </code> | ||
| + | </hidden> | ||
| + | |||
| + | === 例题七 === | ||
| + | |||
| + | [[https://www.luogu.com.cn/problem/P4248|洛谷p4248]] | ||
| + | |||
| + | == 题意 == | ||
| + | |||
| + | 给定字符串 $S$，设 $T_i=S[i,n]$，求 | ||
| + | |||
| + | $$\sum_{1\le i\lt j\le n}|T_i|+|T_j|+2\times \text{LCP}(T_i,T_j)$$ | ||
| + | |||
| + | == 题解 == | ||
| + | |||
| + | $$\sum_{1\le i\lt j\le n}|T_i|+|T_j|-2\times \text{LCP}(T_i,T_j)=(n-1)\sum_{i=1}^n|T_i|-2\times \sum_{1\le i\lt j\le n}\text{LCP}(T_i,T_j)=\frac {(n-1)n(n+1)}2-2\times \sum_{1\le i\lt j\le n}\text{LCP}(T_i,T_j)$$ | ||
| + | |||
| + | 发现只要维护后面部分即可。 | ||
| + | |||
| + | 考虑单调栈维护，设 $\text{dp}_i=\sum_{1\le j\lt i}\text{LCP}(T_i,T_j)$，用单调栈维护 $height_i$ 数组。 | ||
| + | |||
| + | 于是对所有 $i$，可以均摊 $O(1)$ 得到最大的 $j\lt i$ 满足 $\text{hieght}_j\le \text{height}_i$。 | ||
| + | |||
| + | 根据 $\text{height}$ 性质，发现 $j\lt k\le i$ 时 $\text{LCP}(T_k,T_i)=\text{height}_i$，而 $k\le j$ 时 $\text{LCP}(T_k,T_i)=\text{LCP}(T_k,T_j)$。 | ||
| + | |||
| + | 于是 $\text{dp}_i=\sum_{1\le j\lt i}\text{LCP}(T_i,T_j)=\text{dp}_j+(i-j)\text{height}_i$。 | ||
| + | |||
| + | 另外该题也可以用笛卡尔树或并查集等维护。 | ||
| + | |||
| + | <hidden 查看代码> | ||
| + | <code cpp> | ||
| + | const int MAXN=5e5+5,MAXM=20; | ||
| + | namespace SA{ | ||
| + | int sa[MAXN],rk[MAXN],height[MAXN],x[MAXN],y[MAXN],c[MAXN]; | ||
| + | void get_sa(char *s,int n,int m){ | ||
| + | _rep(i,0,m)c[i]=0; | ||
| + | _rep(i,1,n)c[x[i]=s[i]]++; | ||
| + | _rep(i,1,m)c[i]+=c[i-1]; | ||
| + | for(int i=n;i;i--)sa[c[x[i]]--]=i; | ||
| + | for(int k=1;k<n;k<<=1){ | ||
| + | int pos=0; | ||
| + | _rep(i,n-k+1,n)y[++pos]=i; | ||
| + | _rep(i,1,n)if(sa[i]>k)y[++pos]=sa[i]-k; | ||
| + | _rep(i,0,m)c[i]=0; | ||
| + | _rep(i,1,n)c[x[i]]++; | ||
| + | _rep(i,1,m)c[i]+=c[i-1]; | ||
| + | for(int i=n;i;i--)sa[c[x[y[i]]]--]=y[i],y[i]=0; | ||
| + | swap(x,y); | ||
| + | pos=0,y[n+1]=0; | ||
| + | _rep(i,1,n)x[sa[i]]=(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k])?pos:++pos; | ||
| + | if(pos==n)break; | ||
| + | m=pos; | ||
| + | } | ||
| + | _rep(i,1,n)rk[sa[i]]=i; | ||
| + | } | ||
| + | void get_height(char *s,int n){ | ||
| + | for(int i=1,k=0;i<=n;i++){ | ||
| + | if(k)k--; | ||
| + | while(s[i+k]==s[sa[rk[i]-1]+k])k++; | ||
| + | height[rk[i]]=k; | ||
| + | } | ||
| + | } | ||
| + | } | ||
| + | char buf[MAXN]; | ||
| + | pair<int,int> Stack[MAXN]; | ||
| + | LL dp[MAXN]; | ||
| + | int main() | ||
| + | { | ||
| + | scanf("%s",buf+1); | ||
| + | int n=strlen(buf+1); | ||
| + | SA::get_sa(buf,n,'z'); | ||
| + | SA::get_height(buf,n); | ||
| + | LL ans=1LL*(n-1)*n*(n+1)/2; | ||
| + | int top=0; | ||
| + | Stack[0]=make_pair(0,0); | ||
| + | _rep(i,1,n){ | ||
| + | while(top&&Stack[top].second>SA::height[i])top--; | ||
| + | dp[i]=dp[Stack[top].first]+1LL*(i-Stack[top].first)*SA::height[i],ans-=dp[i]*2; | ||
| + | Stack[++top]=make_pair(i,SA::height[i]); | ||
| + | } | ||
| + | enter(ans); | ||
| return 0; | return 0; | ||
| } | } | ||
| </code> | </code> | ||
| </hidden> | </hidden> | ||
2020-2021/teams/legal_string/jxm2001/字符串_3.1598844797.txt.gz · 最后更改: 2020/08/31 11:33 由 jxm2001
