bzoj 3277 串后缀树+子树不同数个数

题目大意

给定\(n\)个字符串和\(k\)

对于每个字符串，输出它有多少个子串至少是\(k\)个字符串的子串(包括自己)

分析

建出广义后缀自动机

至少是\(k\)个字符串的子串就是求子树内不同数个数

考虑怎么统计答案

不要做本质不同子串做傻了

这题是问有多少个子串，子串相同位置不同是可以重复统计的

直接找字符串的每个后缀，它们前缀对应的子串开始位置都是不同的，不会算重

统计的就是每个后缀对应的节点到跟路径上有多少合法

dfs预处理一下树上前缀和就好

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;

}

巴特西

bzoj 3277 串后缀树+子树不同数个数

题目大意

分析

solution

最新文章

热门文章

巴特西

bzoj 3277 串 后缀树+子树不同数个数

题目大意

分析

solution

最新文章

热门文章

bzoj 3277 串后缀树+子树不同数个数