[文章目录]
Description
给定n个字符串，询问每个字符串有多少子串（不包括空串）是所有n个字符串中至少k个字符串的子串？n，k<=10^5
和上一题一样，建广义后缀自动机，标记每个点表示的串的集合，之后直接搜索后缀树吧2333，复杂度O(n√n)
不然的话可以树链的并+线段树维护dfs出栈-1入栈+1+树链的并复杂度nlogn【其实n是广义SAM的点数】
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 101000
typedef long long ll;
ll siz[N<<1];
int n,m,l[N],r[N];
char st[N];
int last,tot=1,ch[N<<1][26],pre[N<<1],dep[N<<1],vis[N<<1],ws[N<<1],sa[N<<1];
void insert(int x)
{
int p=last;
if(ch[p][x])
{
int q=ch[p][x];
if(dep[q]==dep[p]+1) last=q;
else
{
int clo=++tot; last=clo;
memcpy(ch[clo],ch[q],sizeof(ch[q]));
pre[clo]=pre[q],dep[clo]=dep[p]+1,pre[q]=clo;
for(;p&&ch[p][x]==q;p=pre[p]) ch[p][x]=clo;
}
}
else
{
int cur=++tot;
last=cur; dep[cur]=dep[p]+1;
for(;p&&!ch[p][x];p=pre[p]) ch[p][x]=cur;
if(!p) pre[cur]=1;
else
{
int q=ch[p][x];
if(dep[q]==dep[p]+1) pre[cur]=q;
else
{
int clo=++tot;
memcpy(ch[clo],ch[q],sizeof(ch[q]));
dep[clo]=dep[p]+1,pre[clo]=pre[q],pre[q]=pre[cur]=clo;
for(;p&&ch[p][x]==q;p=pre[p]) ch[p][x]=clo;
}
}
}
}
int main()
{
scanf("%d%d",&n,&m);
int i,j,k,p;
for(i=1;i<=n;++i)
{
l[i]=r[i-1]+1;
scanf("%s",st+l[i]);
r[i]=strlen(st+1);
for(last=1,j=l[i];j<=r[i];++j) insert(st[j]-'a');
}
for(i=1;i<=n;++i)
for(p=1,j=l[i];j<=r[i];++j)
{
p=ch[p][st[j]-'a'];
for(k=p;k&&vis[k]!=i;k=pre[k]) siz[k]++,vis[k]=i;
}
for(i=1;i<=tot;++i) ws[dep[i]]++;
for(i=1;i<=tot;++i) ws[i]+=ws[i-1];
for(i=1;i<=tot;++i) sa[ws[dep[i]]--]=i;
for(siz[1]=0,i=2;i<=tot;++i) siz[sa[i]]=siz[pre[sa[i]]]+(siz[sa[i]]>=m)*(dep[sa[i]]-dep[pre[sa[i]]]);
long long ans;
for(i=1;i<=n;++i)
{
ans=0;
for(p=1,j=l[i];j<=r[i];++j) p=ch[p][st[j]-'a'],ans+=siz[p];
printf("%lld ",ans);
}
return 0;
}