bzoj3879 SvT(后缀自动机+虚树)

bzoj

有一个长度为n的仅包含小写字母的字符串S,下标范围为[1,n].

现在有若干组询问,对于每一个询问,我们给出若干个后缀(以其在S中出现的起始位置来表示),求这些后缀两两之间的LCP(LongestCommonPrefix)的长度之和.一对后缀之间的LCP长度仅统计一遍.

题解时间

bzoj3238

完 全 一 致

只不过这个是只选中其中一部分后缀。

bzoj3238可以用SA搞也可以用SAM搞。

这题一样，但是SAM好想。

建完SAM每次询问建虚树，之后和上面那道全统计一样，一个点的贡献为 $ len[x] * \Sigma_{v1,v2} size_{v1} * size_{v2} $ 。

#include<bits/stdc++.h>
using namespace std;
typedef long long lint;
template<typename TP>inline void read(TP &tar)
{
????TP ret=0,f=1;char ch=getchar();
????while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
????while(ch>='0'&&ch<='9'){ret=ret*10+ch-'0';ch=getchar();}
????tar=ret*f;
}
namespace RKK
{
const int N=1000011;
int len,qaq;char str[N];int ip[N];
struct sumireko{int to,ne;}e[N];int he[N],ecnt;
void addline(int f,int t){e[++ecnt].to=t;e[ecnt].ne=he[f],he[f]=ecnt;}
struct remilia{int tranc[26],len,pre;}s[N];
int fin=1,size=1;
void ins(int ch)
{
????int npx,npy,lpx,lpy;
????npx=++size,lpx=fin,s[npx].len=s[lpx].len+1;
????for(;lpx&&!s[lpx].tranc[ch];lpx=s[lpx].pre) s[lpx].tranc[ch]=npx;
????if(!lpx) s[npx].pre=1;
????else
????{
????????lpy=s[lpx].tranc[ch];
????????if(s[lpy].len==s[lpx].len+1) s[npx].pre=lpy;
????????else
????????{
????????????npy=++size;
????????????s[npy]=s[lpy],s[npy].len=s[lpx].len+1;
????????????s[npx].pre=s[lpy].pre=npy;
????????????while(s[lpx].tranc[ch]==lpy)
????????????????s[lpx].tranc[ch]=npy,lpx=s[lpx].pre;
????????}
????}
????fin=npx;
}
int sp[N],ep[N],fa[N],top[N],dep[N],sz[N],dson[N],da;
void dfs(int x)
{
????sz[x]=1;
????for(int i=he[x],t=e[i].to;i;i=e[i].ne,t=e[i].to)
????????fa[t]=x,dep[t]=dep[x]+1,dfs(t),sz[x]+=sz[t],dson[x]=(sz[t]>sz[dson[x]]?t:dson[x]);
}
void dfs(int x,int tp)
{
????top[x]=tp,sp[x]=++da;
????if(dson[x]) dfs(dson[x],tp);
????for(int i=he[x],t=e[i].to;i;i=e[i].ne,t=e[i].to)if(t!=dson[x])
????????dfs(t,t);
????ep[x]=da;
}
int lca(int x,int y)
{
????while(top[x]!=top[y]) dep[top[x]]>dep[top[y]]?x=fa[top[x]]:y=fa[top[y]];
????return dep[x]<dep[y]?x:y;
}
lint ans;
bool use[N];
int work(int x)
{
????int sx=use[x];
????for(int i=he[x],t=e[i].to,st;i;i=e[i].ne,t=e[i].to)
????????st=work(t),ans+=1ll*s[x].len*sx*st,sx+=st;
????return sx;
}
?
int lst[N],ln;
int sta[N],stp;
bool cmp(const int &a,const int &b){return sp[a]<sp[b];}
int Iris()
{
????scanf("%d%d%s",&len,&qaq,str+1);
????for(int i=len;i;i--) ins(str[i]-'a'),ip[i]=fin;
????for(int i=2;i<=size;i++) addline(s[i].pre,i);
????dfs(1),dfs(1,1);memset(he,0,sizeof(he)),ecnt=0;
????for(int rkk=1;rkk<=qaq;rkk++)
????{
????????read(ln),stp=0,ans=0;for(int i=1,x;i<=ln;i++) read(x),lst[i]=ip[x],use[lst[i]]=1;
????????sort(lst+1,lst+1+ln,cmp);
????????for(int i=1,lim=ln;i<lim;i++) lst[++ln]=lca(lst[i],lst[i+1]);
????????sort(lst+1,lst+1+ln,cmp),ln=unique(lst+1,lst+1+ln)-lst-1;
????????for(int i=1;i<=ln;i++)
????????{
????????????while(stp&&ep[sta[stp]]<sp[lst[i]]) stp--;
????????????addline(sta[stp],lst[i]),sta[++stp]=lst[i];
????????}
????????work(lst[1]),printf("%lld\n",ans);
????????for(int i=1;i<=ln;i++) use[lst[i]]=0,he[lst[i]]=0;ecnt=0;
????}
????return 0;
}
}
int main(){return RKK::Iris();}

bzoj3879 SvT(后缀自动机+虚树)

原文：https://www.cnblogs.com/rikurika/p/12099226.html