一道sam練習題

題意

解法

考慮答案實際上是每個子串的出現次數的平方和.

這個可以通過手玩樣例驗證.

考慮廣義sam:先将所有字元串建成trie,然後再在trie上bfs,建出sam.

考慮fail樹

每次插入一個新節點,會改變從這個節點開始到根的路徑上的每個節點的right集合大小.

是以考慮樹剖維護這種操作,然後每一個單詞的答案就是之前所有單詞的答案,再計算自己的答案,然後注意這裡一個線段樹節點維護的有sam上這段區間總共的本質不同子串數量,要求的答案和修改标記

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+5;
int n,m;
long long ans;
int s[maxn];
int tot,trie[maxn][26],ch[maxn][26],len[maxn],sz[maxn],en[maxn],fa[maxn];
vector<int> e[maxn];
int son[maxn],last[maxn],fail[maxn];
inline void insert(int c,int ed){
	//printf("%lld %lld\n",c,ed);
	int p=ed,np=++tot;
	len[np]=len[p]+1;
	for(;p&&(!ch[p][c]);p=fail[p])ch[p][c]=np;
	if(!p){fail[np]=1;}
	else{
		int q=ch[p][c];
		if(len[q]==len[p]+1)fail[np]=q;
		else{
			int nq=++tot;
			len[nq]=len[p]+1;
			for(int i=0;i<26;i++)ch[nq][i]=ch[q][i];
			fail[nq]=fail[q];fail[q]=fail[np]=nq;
			for(;p&&ch[p][c]==q;p=fail[p])ch[p][c]=nq;
		}
	}
}
void bfs(){
	queue<int> q;
	while(!q.empty())q.pop();
	q.push(1);
	while(!q.empty()){
		int x=q.front();q.pop();
		//printf("%lld %lld\n",x,last[x]);
		for(int i=0;i<26;i++){
			if(trie[x][i]){
				//printf("%lld %lld\n",x,trie[x][i]);
				q.push(trie[x][i]);
				last[trie[x][i]]=tot+1;
				insert(i,last[x]);
			}
		}
	}
}
void dfs1(int u){
	sz[u]=1;
	for(int i=0;i<e[u].size();i++){
		int v=e[u][i];
		dfs1(v);fa[v]=u;
		sz[u]+=sz[v];
		if(sz[v]>sz[son[u]])son[u]=v;
	}
}
int top[maxn],dfn[maxn],tim;
void dfs2(int u,int tp){
	//printf("%lld\n",u);
	top[u]=tp;dfn[u]=++tim;
	if(son[u]){
		dfs2(son[u],tp);
	}
	for(int i=0;i<e[u].size();i++){
		int v=e[u][i];
		if(v==son[u])continue;
		dfs2(v,v);
	}
}
struct node{
	long long v,s,tag;
}t[maxn<<2];
#define ls rt<<1
#define rs rt<<1|1
inline void pushup(int rt){
	t[rt].s=t[ls].s+t[rs].s;
}
void build(int rt,int l,int r,int x,int y){
	if(l==r){
		t[rt].v=len[y]-len[fail[y]];
		return ;
	}
	int mid=(l+r)>>1;
	if(x<=mid)build(ls,l,mid,x,y);
	else build(rs,mid+1,r,x,y);
	t[rt].v=t[ls].v+t[rs].v;
}
void pushdown(int rt){
	if(t[rt].tag){
		int tmp=t[rt].tag;
		t[ls].tag+=tmp;t[rs].tag+=tmp;
		t[ls].s+=tmp*t[ls].v;
		t[rs].s+=tmp*t[rs].v;
		t[rt].tag=0;
	}
}
void ins(int rt,int l,int r,int x,int y){
	if(x<=l&&r<=y){
		t[rt].tag++;
		t[rt].s=t[rt].s+t[rt].v;
		return ;
	}
	int mid=(l+r)>>1;pushdown(rt);
	if(x<=mid)ins(ls,l,mid,x,y);
	if(y>mid)ins(rs,mid+1,r,x,y);
	pushup(rt);
}
void get(int rt,int l,int r,int x,int y){
	if(x<=l&&r<=y){
		ans+=t[rt].s;
		return ;
	}
	pushdown(rt);
	int mid=(l+r)>>1;
	if(x<=mid)get(ls,l,mid,x,y);
	if(y>mid)get(rs,mid+1,r,x,y);
}
void calc(int x){
	x=last[x];
	int y=x;
	while(y>1){
		x=top[y];
		get(1,1,m,dfn[x],dfn[y]);
		y=fa[x];
	}
}
void change(int x){
	x=last[x];
	int y=x;
	while(y>1){
		x=top[y];
		ins(1,1,m,dfn[x],dfn[y]);
		y=fa[x];
	}
}
signed main(){
	//freopen("3.in","r",stdin);
	//freopen("3.out","w",stdout);
	scanf("%d\n",&n);
	tot=1;
	for(int i=1;i<=n;i++){
		int c=getchar()-'a';
		int x=1;en[i]=en[i-1];
		for(;c>=0&&c<26;c=getchar()-'a'){
			if(trie[x][c]==0)trie[x][c]=++tot;
			x=trie[x][c];s[++en[i]]=c;
		}
	}
	//printf("%lld\n",tot);
	//return 0;
	last[1]=1;tot=1;bfs();
	//printf("%lld\n",tot);
	m=tot;tot=0;
	for(int i=2;i<=m;i++)e[fail[i]].push_back(i);
	tot=0;dfs1(1);son[1]=0;dfs2(1,0);
	for(int i=1;i<=m;i++){
		//printf("%lld ",last[i]);
		build(1,1,m,dfn[i],i);
	}
	//return 0;
	for(int i=1;i<=n;i++){
		int x=1;
		for(int j=en[i-1]+1;j<=en[i];j++){
			x=trie[x][s[j]];
			calc(x);
		}
		x=1;
		for(int j=en[i-1]+1;j<=en[i];j++){
			x=trie[x][s[j]];
			change(x);
		}
		x=1;
		for(int j=en[i-1]+1;j<=en[i];j++){
			x=trie[x][s[j]];
			calc(x);
		}
		printf("%lld\n",ans);
	}
	return 0;
}