题意：

给你n个串，对于每个串求出只包含在这个串中的本质不同子串数量。

$n,\sum |S| \leq 10^5.$

 

题解：

广义sam，right集合定义为多个串中出现的位置的并。

某个子串只出现在一个串中等价于当前状态的right集合只属于一个串。令f[u]表示u状态的right集合属于哪个串，若属于多个串记为-1，建出树以后自下而上合并right即可。

复杂度$\mathcal{O}(n)$。

 

code：

1 #include
      
        2 #define rep(i,x,y) for (int i=(x);i<=(y);i++) 3 #define ll long long 4 #define inf 1000000001 5 #define y1 y1___ 6 using namespace std; 7 char gc(){ 8     static char buf[100000],*p1=buf,*p2=buf; 9     return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;10 }11 #define gc getchar12 ll read(){13     char ch=gc();ll x=0;int op=1;14     for (;!isdigit(ch);ch=gc()) if (ch=='-') op=-1;15     for (;isdigit(ch);ch=gc()) x=(x<<1)+(x<<3)+ch-'0';16     return x*op;17 }18 #define N 20000519 int n,tot=1,rt=1,last=1,fa[N],ch[N][30],len[N],f[N],head[N],cnt,ans[N];char str[N];20 struct edge{
    int to,nxt;}e[N];21 void adde(int x,int y){22     e[++cnt].to=y;e[cnt].nxt=head[x];head[x]=cnt;23 }24 void extend(int c,int id){
    //广义sam，right集合定义为多个串中出现的位置的并25     int p=last,np=last=++tot,q,nq;len[np]=len[p]+1;26     for (;p&&!ch[p][c];p=fa[p]) ch[p][c]=np;27     if (!p) fa[np]=rt;28     else{29         q=ch[p][c];30         if (len[q]==len[p]+1) fa[np]=q;31         else{32             nq=++tot;len[nq]=len[p]+1;33             memcpy(ch[nq],ch[q],sizeof(ch[q]));34             fa[nq]=fa[q];fa[np]=fa[q]=nq;35             for (;p&&ch[p][c]==q;p=fa[p]) ch[p][c]=nq;36         }37     }38     if (f[np]&&f[np]!=id) f[np]=-1;else f[np]=id;39 }40 void dfs(int u){41     for (int i=head[u];i;i=e[i].nxt) dfs(e[i].to);42     if (f[u]&&f[u]!=-1) ans[f[u]]+=len[u]-len[fa[u]];43     if (f[fa[u]]&&f[fa[u]]!=f[u]) f[fa[u]]=-1;else f[fa[u]]=f[u];44 }45 int main(){46     n=read();47     rep (i,1,n){48         scanf("%s",str+1);int l=strlen(str+1);49         last=rt;50         rep (j,1,l) extend(str[j]-'a',i);51     }52     rep (i,2,tot) adde(fa[i],i);53     dfs(rt);54     rep (i,1,n) printf("%d\n",ans[i]);55     return 0;56 }