【题目】
lydsy
给定n个字符串,对于每个字符串,问只在这个字符串中出现的子串有多少个。
n,∑∣S∣≤105
【解题思路】
随便写写板子吧。
建出广义SAM后自下而上合并right集合即可,实现时就是给每个结束节点打个颜色标记,若标记相同就设成−1就好了。
试图冲榜一但失败了。
【参考代码】
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int n,f[N],b[N],c[N];
long long ans[N];
char s[N];
struct SAM
{
int sz,las,fa[N],mx[N],ch[N][26];
void extend(int x)
{
int p,np,q,nq;
if(ch[las][x])
{
p=las;las=q=ch[p][x];//be careful here, las=ch[p][x]
if(mx[q]==mx[p]+1) return;
las=nq=++sz;mx[nq]=mx[p]+1;
memcpy(ch[nq],ch[q],sizeof(ch[q]));
fa[nq]=fa[q];fa[q]=nq;
for(;p && ch[p][x]==q;p=fa[p]) ch[p][x]=nq;
return;
}
p=las;np=las=++sz;mx[np]=mx[p]+1;
for(;p && !ch[p][x];p=fa[p]) ch[p][x]=np;
if(!p) fa[np]=1;
else
{
q=ch[p][x];
if(mx[q]==mx[p]+1) fa[np]=q;
else
{
nq=++sz;mx[nq]=mx[p]+1;
memcpy(ch[nq],ch[q],sizeof(ch[q]));
fa[nq]=fa[q];fa[q]=fa[np]=nq;
for(;p && ch[p][x]==q;p=fa[p]) ch[p][x]=nq;
}
}
}
void merge()
{
for(int i=1;i<=sz;++i) b[mx[i]]++;
for(int i=1;i<=sz;++i) b[i]+=b[i-1];
for(int i=sz;i;--i) c[b[mx[i]]--]=i;
for(int i=sz,x;i;--i)
{
x=c[i];
if(~f[x]) ans[f[x]]+=mx[x]-mx[fa[x]];
if(f[fa[x]] && f[fa[x]]!=f[x]) f[fa[x]]=-1; else f[fa[x]]=f[x];
}
}
}T;
int main()
{
#ifdef Durant_Lee
freopen("BZOJ5137.in","r",stdin);
freopen("BZOJ5137.out","w",stdout);
#endif
scanf("%d",&n);T.sz=1;
for(int i=1;i<=n;++i)
{
T.las=1;scanf("%s",s+1);int len=strlen(s+1);
for(int j=1;j<=len;++j)
{
T.extend(s[j]-'a');
if(!f[T.las]) f[T.las]=i; else f[T.las]=-1;
}
}
T.merge();
for(int i=1;i<=n;++i) printf("%lld",ans[i]),putchar('\n');
return 0;
}