【LuoguP4081】[USACO17DEC]Standing Out from the Herd

題目連結

題意

給定多個字元串，每個串中僅在該串中出現的本質不同的子串個數。

Sol

多串比對想到用廣義SAM。

之後從串的比對角度不是很好做。發現一個本質不同的串最多隻會貢獻到一個串的答案裡。

那麼建完廣義SAM後，如果我們能夠知道那些點是隻有一個串能夠到達并且知道是哪個的話我們就可以直接把這個點代表的本質不同的串給貢獻到對應串的答案中。

這個很好辦，我們在建廣義SAM的時候不考慮串之間的比對，建完後再拿着所有的串重新在廣義SAM上跑一遍，當我們周遊到一個點(也就是該串的一個字首)的時候，它的祖先鍊上的所有點就都是存在于這個串中的子串，對目前點打上一個标記。如果已有不同标記說明這個點以及它所有的祖先都不會對任何一個串的答案産生貢獻，那麼直接變成-1表示不對答案産生貢獻。

之後我們對 parent 樹dfs求出每一個點的狀态并且貢獻答案就行了。

code:

#include<bits/stdc++.h>
using namespace std;
#define Set(a,b) memset(a,b,sizeof(a))
#define Copy(a,b) memcpy(a,b,sizeof(a))
template<class T>inline void init(T&x){
	x=0;char ch=getchar();bool t=0;
	for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') t=1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<1)+(x<<3)+(ch-48);
	if(t) x=-x;return;
}typedef long long ll;
const int N=1e5+10;
const int MAXN=N<<1;
ll ans[N];char S[N];
int son[MAXN][26],pass[MAXN],len[MAXN],length[N],fa[MAXN];
int lst=0,node=0;

struct edge{
	int to,next;
}a[N<<1];
int head[N<<1],cnt=0;
inline void add(int x,int y){a[++cnt]=(edge){y,head[x]};head[x]=cnt;}
int n;
void Extend(int c){
	if(son[lst][c]&&len[son[lst][c]]==len[lst]+1) lst=son[lst][c];
	else {
		int p=++node,u=lst;lst=p;len[p]=len[u]+1;
		while(~u&&!son[u][c]) son[u][c]=p,u=fa[u];
		if(~u) {
			int v=son[u][c];
			if(len[v]==len[u]+1) return void(fa[p]=v);
			int q=++node;Copy(son[q],son[v]);
			fa[q]=fa[v];len[q]=len[u]+1;fa[v]=fa[p]=q;
			while(~u&&son[u][c]==v) son[u][c]=q,u=fa[u];
		}
	}return;
}
void Insert(char*s,int L){
	lst=0;fa[0]=-1;
	for(int i=1;i<=L;++i) Extend(s[i]-'a');
	return;
}
void GO(char*s,int id,int L){
	int u=0;
	for(int i=1;i<=L;++i) {
		int c=s[i]-'a';
		u=son[u][c];
		if(pass[u]>0) pass[u]=-1;
		else if(!pass[u]) pass[u]=id;
	}
}
void Dfs(int u){
	for(int v,i=head[u];i;i=a[i].next) {
		v=a[i].to;Dfs(v);
		if(~pass[u]) {
			if(!pass[u]) pass[u]=pass[v];
			else if(pass[u]!=pass[v]) pass[u]=-1;
		}
	}
	if(pass[u]>0) ans[pass[u]]+=len[u]-len[fa[u]];
}
int main()
{
	int L=0;init(n);
	for(int i=1;i<=n;++i) {
		scanf("%s",S+1+L);
		length[i]=strlen(S+1+L);
		Insert(S+L,length[i]);
		L+=length[i];
	}
	for(int i=1;i<=node;++i) add(fa[i],i);L=0;
	for(int i=1;i<=n;++i) GO(S+L,i,length[i]),L+=length[i];
	Dfs(0);
	for(int i=1;i<=n;++i) printf("%lld\n",ans[i]);
	return 0;
}