題目大意

給定\(n\)個(gè)字符串和\(k\)
對(duì)于每個(gè)字符串，輸出它有多少個(gè)子串至少是\(k\)個(gè)字符串的子串(包括自己)

分析

建出廣義后綴自動(dòng)機(jī)
至少是\(k\)個(gè)字符串的子串就是求子樹(shù)內(nèi)不同數(shù)個(gè)數(shù)
考慮怎么統(tǒng)計(jì)答案

不要做本質(zhì)不同子串做傻了
這題是問(wèn)有多少個(gè)子串，子串相同位置不同是可以重復(fù)統(tǒng)計(jì)的

直接找字符串的每個(gè)后綴，它們前綴對(duì)應(yīng)的子串開(kāi)始位置都是不同的，不會(huì)算重
統(tǒng)計(jì)的就是每個(gè)后綴對(duì)應(yīng)的節(jié)點(diǎn) 到跟路徑上 有多少合法
dfs預(yù)處理一下樹(shù)上前綴和就好

solution

#include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <cmath> #include <algorithm> using namespace std; typedef long long LL; const int M=200007;inline int rd(){int x=0;bool f=1;char c=getchar();for(;!isdigit(c);c=getchar()) if(c=='-') f=0;for(;isdigit(c);c=getchar()) x=x*10+c-48;return f?x:-x; }LL sum[M]; int n,m; char s[M]; int last,tot; int stp[M]; int ch[M][26]; int fa[M]; int que[M],ed[M]; int q[M],tq; int dfn[M],sz[M],tdfn; int pre[M][20],Mx,dep[M];struct edge{int y,nxt;}; struct vec{int g[M],te;edge e[M];vec(){memset(g,0,sizeof(g));te=0;}void clear(){memset(g,0,sizeof(g));te=0;}inline void push(int x,int y){e[++te].y=y;e[te].nxt=g[x];g[x]=te;}inline int& operator () (int &x){return g[x];}inline edge& operator [] (int &x){return e[x];} }go;int newnode(int ss){stp[++tot]=ss;return tot; }int ext(int p,int q,int d){int nq=newnode(stp[p]+1);fa[nq]=fa[q]; fa[q]=nq;memcpy(ch[nq],ch[q],sizeof(ch[q]));for(;p&&ch[p][d]==q;p=fa[p]) ch[p][d]=nq;return nq; }int sam(int p,int d){int np=ch[p][d];if(np) return (stp[p]+1==stp[np]) ? np : ext(p,np,d);np=newnode(stp[p]+1);for(;p&&!ch[p][d];p=fa[p]) ch[p][d]=np;if(!p) fa[np]=1;else{int q=ch[p][d];fa[np]= (stp[p]+1==stp[q]) ? q : ext(p,q,d);}return np; }int dfs(int x){dfn[x]=++tdfn;sz[x]=1;int p,y;for(p=go(x);p;p=go[p].nxt){y=go[p].y;dep[y]=dep[x]+1;pre[y][0]=x;dfs(y);sz[x]+=sz[y];} }bool cmp(int x,int y){return dfn[x]<dfn[y]; }int LCA(int x,int y){if(dep[x]<dep[y]) swap(x,y);for(int t=Mx;t>=0;t--)if(dep[pre[x][t]]>=dep[y]) x=pre[x][t];if(x==y) return x;for(int t=Mx;t>=0;t--)if(pre[x][t]!=pre[y][t]) x=pre[x][t],y=pre[y][t];return pre[x][0]; }int c[M];inline int lb(int x){return x&(-x);}inline int add(int x,int d){for(;x<=tdfn;x+=lb(x)) c[x]+=d; }inline int get(int x){int res=0;for(;x>0;x-=lb(x)) res+=c[x];return res; }inline int get(int x,int y){return get(y)-get(x-1); }void vtree(int l,int r){int i,x,p,y;tq=0;for(i=l;i<=r;i++) q[++tq]=que[i];sort(q+1,q+tq+1,cmp);for(i=1;i<=tq;i++) add(dfn[q[i]],1);for(i=2;i<=tq;i++) add(dfn[LCA(q[i],q[i-1])],-1); }void gao(int x){int p,y;for(p=go(x);p;p=go[p].nxt){y=go[p].y;if(get(dfn[y],dfn[y]+sz[y]-1)>=m) sum[y]=sum[x]+stp[y]-stp[x];else sum[y]=sum[x];gao(y);} }int main(){int i,j,p;n=rd(),m=rd();tot=1;for(i=1;i<=n;i++){scanf("%s",s+1);last=1;p=strlen(s+1);for(j=p;j>0;j--){last=sam(last,s[j]-'a');//***que[++tq]=last;}ed[i]=tq;}for(i=2;i<=tot;i++) go.push(fa[i],i);dfs(1);Mx=log2(tot);for(j=1;j<=Mx;j++)for(i=1;i<=tot;i++) pre[i][j]=pre[pre[i][j-1]][j-1];for(i=1;i<=n;i++) vtree(ed[i-1]+1,ed[i]);gao(1);for(i=1;i<=n;i++){LL ans=0;for(j=ed[i-1]+1;j<=ed[i];j++)ans+=sum[que[j]];printf("%lld\n",ans);}return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/acha/p/6581283.html

總結(jié)

以上是生活随笔為你收集整理的bzoj 3277 串 后缀树+子树不同数个数的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。