在搞广义后缀自动机之前，先做一个后缀自动机的题目，练练手。
好吧。又忘了%mmh学长了。wa了好久。
%mmh
①：Cool Slogans CodeForces - 700E：
Bomboslav set up a branding agency and now helps companies to create new logos and advertising slogans. In term of this problems, slogan of the company should be a non-empty substring of its name. For example, if the company name is “hornsandhoofs”, then substrings “sand” and “hor” could be its slogans, while strings “e” and “hornss” can not.
Sometimes the company performs rebranding and changes its slogan. Slogan A is considered to be cooler than slogan B if B appears in A as a substring at least twice (this occurrences are allowed to overlap). For example, slogan A = “abacaba” is cooler than slogan B = “ba”, slogan A = “abcbcbe” is cooler than slogan B = “bcb”, but slogan A = “aaaaaa” is not cooler than slogan B = “aba”.
You are given the company name w and your task is to help Bomboslav determine the length of the longest sequence of slogans s1, s2, …, sk, such that any slogan in the sequence is cooler than the previous one.
Input
The first line of the input contains a single integer n (1 ≤ n ≤ 200 000) — the length of the company name that asks Bomboslav to help. The second line contains the string w of length n, that consists of lowercase English letters.
Output
Print a single integer — the maximum possible length of the sequence of slogans of the company named w, such that any slogan in the sequence (except the first one) is cooler than the previous
Examples
Input
3
abc
Output
1
Input
5
ddddd
Output
5
Input
11
abracadabra
Output
3
题意：给出一个长度为n的字符串s[1]，由小写字母组成。定义一个字符串序列s[1…k],满足性质：s[i]在s[i-1] (i>=2)中出现至少两次（位置可重叠），问最大的k是多少，使得从s[1]开始到s[k]都满足这样一个性质。
题解：在parent树上从上到下dp，转移是父节点代表串是否在子节点代表串中出现两次，注意隔代转移的情况。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#define ll long long
#define llu unsigned ll
using namespace std;
const int maxn=200100;
char str[maxn];
struct Sam
{
int last,cnt,tot;
int nt[maxn<<1][26],fa[maxn<<1];
int len[maxn<<1],sum[maxn<<1];
int x[maxn<<1],y[maxn<<1],pos[maxn<<1];
int maxx[maxn<<1],top[maxn<<1];
int root[maxn<<1],n;
struct node
{
int lc,rc;
int sum;
}t[maxn*50];
int newnode(void)
{
int p=++tot;
t[p].lc=t[p].rc=t[p].sum=0;
return p;
}
int in(int p,int l,int r,int id)
{
if(!p) p=newnode();
if(l==r)
{
t[p].sum=1;
return p;
}
int mid=(l+r)>>1;
if(id<=mid) t[p].lc=in(t[p].lc,l,mid,id);
else t[p].rc=in(t[p].rc,mid+1,r,id);
t[p].sum=t[t[p].lc].sum+t[t[p].rc].sum;
return p;
}
int _merge(int p,int q,int l,int r)
{
if(!p) return q;
if(!q) return p;
int now=newnode();
if(l==r)
{
t[now].sum=t[p].sum+t[q].sum;
return now;
}
int mid=(l+r)>>1;
t[now].lc=_merge(t[p].lc,t[q].lc,l,mid);
t[now].rc=_merge(t[p].rc,t[q].rc,mid+1,r);
t[now].sum=t[t[now].lc].sum+t[t[now].rc].sum;
return now;
}
bool ask(int p,int nl,int nr,int l,int r)
{
if(t[p].sum==0) return false;
if(nl<=l&&r<=nr)
{
if(t[p].sum) return true;
else return false;
}
int mid=(l+r)>>1;
if(nl<=mid) if(ask(t[p].lc,nl,nr,l,mid)) return true;
if(nr>mid) if(ask(t[p].rc,nl,nr,mid+1,r)) return true;
return false;
}
void init(void)
{
tot=0;
t[0].lc=t[0].rc=t[0].sum=0;
last=1;
cnt=1;
fa[1]=0;
len[1]=0;
}
void _insert(int c,int id)
{
int nowp=++cnt,p=last;
len[nowp]=len[last]+1,pos[nowp]=id;
while(p&&!nt[p][c]) nt[p][c]=nowp,p=fa[p];
if(!p) fa[nowp]=1;
else
{
int q=nt[p][c];
if(len[q]==len[p]+1) fa[nowp]=q;
else
{
int nowq=++cnt;
len[nowq]=len[p]+1,pos[nowq]=pos[q];
memcpy(nt[nowq],nt[q],sizeof(nt[q]));
fa[nowq]=fa[q];
fa[nowp]=fa[q]=nowq;
while(p&&nt[p][c]==q) nt[p][c]=nowq,p=fa[p];
}
}
last=nowp;
sum[last]=1;
root[last]=in(root[last],1,n,id);
return ;
}
void _count(void)
{
memset(x,0,sizeof(x));
for(int i=1;i<=cnt;i++) x[len[i]]++;
for(int i=1;i<=cnt;i++) x[i]+=x[i-1];
for(int i=1;i<=cnt;i++) y[x[len[i]]--]=i;
for(int i=cnt;i>=1;i--)
sum[fa[y[i]]]+=sum[y[i]];
for(int i=cnt;i>1;i--)
root[fa[y[i]]]=_merge(root[fa[y[i]]],root[y[i]],1,n);
return ;
}
void creat(void)
{
int len=strlen(str+1);
n=len;
init();
for(int i=1;i<=len;i++)
_insert(str[i]-'a',i);
_count();
return ;
}
int get_max(void)
{
int ans=0;
for(int i=2;i<=cnt;i++)
{
int x=y[i],fx=fa[x];
if(fx==1)
maxx[x]=1,top[x]=x;
else
{
if(ask(root[top[fx]],pos[x]-len[x]+len[top[fx]],pos[x]-1,1,n))
maxx[x]=maxx[fx]+1,top[x]=x;
else maxx[x]=maxx[fx],top[x]=top[fx];
}
ans=max(ans,maxx[x]);
}
return ans;
}
}sam;
int main(void)
{
int n;
scanf("%d%s",&n,str+1);
sam.creat();
printf("%d\n",sam.get_max());
return 0;
}
广义后缀自动机就先做一个模板题把，以后再补上。
②：BZOJ 3277
给定n个字符串，询问每个字符串有多少子串（不包括空串）是所有n个字符串中至少k个字符串的子串（包括本身）。
跑广义sam，求某个节点代表的串是多少个字符串的子串。
写法一：假—广义sam
//508ms
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#include<cstdlib>
#include<string>
#define ll long long
#define llu unsigned ll
using namespace std;
const int maxn=100100;
const int root=1;
struct Sam
{
int last,cnt;
int n,k;
int nt[maxn<<1][26],fa[maxn<<1];
int len[maxn<<1],sum[maxn<<1];
int x[maxn<<1],y[maxn<<1];
int ha[maxn<<1],f[maxn<<1];
string a[maxn];
char str[maxn];
void init(void)
{
last=root;
cnt=1;
fa[1]=0;
len[1]=0;
}
void _insert(int c)
{
int nowp=++cnt,p=last;
len[nowp]=len[last]+1;
while(p&&!nt[p][c]) nt[p][c]=nowp,p=fa[p];
if(!p) fa[nowp]=root;
else
{
int q=nt[p][c];
if(len[q]==len[p]+1) fa[nowp]=q;
else
{
int nowq=++cnt;
len[nowq]=len[p]+1;
memcpy(nt[nowq],nt[q],sizeof(nt[q]));
fa[nowq]=fa[q];
fa[nowp]=fa[q]=nowq;
while(p&&nt[p][c]==q) nt[p][c]=nowq,p=fa[p];
}
}
last=nowp;
return ;
}
void _count(void)
{
memset(x,0,sizeof(x));
for(int i=1;i<=cnt;i++) x[len[i]]++;
for(int i=1;i<=cnt;i++) x[i]+=x[i-1];
for(int i=1;i<=cnt;i++) y[x[len[i]]--]=i;
}
void creat(void)
{
init();
for(int i=1;i<=n;i++)
{
scanf("%s",str);
a[i]=string(str);
last=root;
int len=strlen(str);
for(int j=0;j<len;j++)
_insert(str[j]-'a');
}
_count();
return ;
}
void get_ans(void)
{
for(int i=1;i<=n;i++)
{
int p=root;
for(int j=0;j<a[i].size();j++)
{
p=nt[p][a[i][j]-'a'];
int np=p;
while(np&&ha[np]!=i) sum[np]++,ha[np]=i,np=fa[np];
}
}
}
void get_f(void)
{
f[root]=0;
for(int i=2;i<=cnt;i++)
f[y[i]]=f[fa[y[i]]]+(sum[y[i]]>=k?len[y[i]]-len[fa[y[i]]]:0);
}
void print_ans(void)
{
get_f();
for(int i=1;i<=n;i++)
{
int ans=0;
int p=root;
for(int j=0;j<a[i].size();j++)
{
p=nt[p][a[i][j]-'a'];
ans+=f[p];
}
printf("%d ",ans);
}
return ;
}
}sam;
int main(void)
{
scanf("%d%d",&sam.n,&sam.k);
sam.creat();
sam.get_ans();
sam.print_ans();
return 0;
}
写法二：真—广义sam
在线建立法，dfs
//480ms
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#include<cstdlib>
#include<string>
#define ll long long
#define llu unsigned ll
using namespace std;
const int maxn=100100;
const int root=1;
struct Sam
{
int last,cnt;
int n,k;
int nt[maxn<<1][26],fa[maxn<<1];
int len[maxn<<1],sum[maxn<<1];
int x[maxn<<1],y[maxn<<1];
int ha[maxn<<1],f[maxn<<1];
string a[maxn];
char str[maxn];
void init(void)
{
last=root;
cnt=1;
fa[1]=0;
len[1]=0;
}
void _insert(int c)
{
if(nt[last][c])
{
int p=last,q=nt[p][c];
if(len[q]==len[p]+1) last=q;
else
{
int nowq=++cnt;
len[nowq]=len[p]+1;
memcpy(nt[nowq],nt[q],sizeof(nt[q]));
fa[nowq]=fa[q];
fa[q]=nowq;
while(p&&nt[p][c]==q) nt[p][c]=nowq,p=fa[p];
last=nowq;
}
}
else
{
int nowp=++cnt,p=last;
len[nowp]=len[last]+1;
while(p&&!nt[p][c]) nt[p][c]=nowp,p=fa[p];
if(!p) fa[nowp]=root;
else
{
int q=nt[p][c];
if(len[q]==len[p]+1) fa[nowp]=q;
else
{
int nowq=++cnt;
len[nowq]=len[p]+1;
memcpy(nt[nowq],nt[q],sizeof(nt[q]));
fa[nowq]=fa[q];
fa[nowp]=fa[q]=nowq;
while(p&&nt[p][c]==q) nt[p][c]=nowq,p=fa[p];
}
}
last=nowp;
}
return ;
}
void _count(void)
{
memset(x,0,sizeof(x));
for(int i=1;i<=cnt;i++) x[len[i]]++;
for(int i=1;i<=cnt;i++) x[i]+=x[i-1];
for(int i=1;i<=cnt;i++) y[x[len[i]]--]=i;
}
void creat(void)
{
init();
for(int i=1;i<=n;i++)
{
scanf("%s",str);
a[i]=string(str);
last=root;
int len=strlen(str);
for(int j=0;j<len;j++)
_insert(str[j]-'a');
}
_count();
return ;
}
void get_ans(void)
{
for(int i=1;i<=n;i++)
{
int p=root;
for(int j=0;j<a[i].size();j++)
{
p=nt[p][a[i][j]-'a'];
int np=p;
while(np&&ha[np]!=i) sum[np]++,ha[np]=i,np=fa[np];
}
}
}
void get_f(void)
{
f[root]=0;
for(int i=2;i<=cnt;i++)
f[y[i]]=f[fa[y[i]]]+(sum[y[i]]>=k?len[y[i]]-len[fa[y[i]]]:0);
}
void print_ans(void)
{
get_f();
for(int i=1;i<=n;i++)
{
int ans=0;
int p=root;
for(int j=0;j<a[i].size();j++)
{
p=nt[p][a[i][j]-'a'];
ans+=f[p];
}
printf("%d ",ans);
}
return ;
}
}sam;
int main(void)
{
scanf("%d%d",&sam.n,&sam.k);
sam.creat();
sam.get_ans();
sam.print_ans();
return 0;
}
写法三：真—广义sam ：
离线建立 bfs
理论时间复杂度是要比在线建立要低的。。可是为什么跑起来比在线的要慢啊。。。。
//608ms
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#include<cstdlib>
#include<string>
#define ll long long
#define llu unsigned ll
using namespace std;
const int maxn=100100;
const int root=1;
struct Sam
{
int cnt,tot;
int n,k;
int t[maxn][26],q1[maxn],q2[maxn];
int nt[maxn<<1][26],fa[maxn<<1];
int len[maxn<<1],sum[maxn<<1];
int x[maxn<<1],y[maxn<<1];
int ha[maxn<<1],f[maxn<<1];
string a[maxn];
char str[maxn];
void in(void)
{
int len=strlen(str),p=1;
for(int i=0;i<len;i++)
{
int k=str[i]-'a';
if(t[p][k]==0) t[p][k]=++tot;
p=t[p][k];
}
}
void init(void)
{
cnt=1;
tot=1;
fa[1]=0;
len[1]=0;
}
int _insert(int last,int c)
{
int nowp=++cnt,p=last;
len[nowp]=len[last]+1;
while(p&&!nt[p][c]) nt[p][c]=nowp,p=fa[p];
if(!p) fa[nowp]=1;
else
{
int q=nt[p][c];
if(len[q]==len[p]+1) fa[nowp]=q;
else
{
int nowq=++cnt;
len[nowq]=len[p]+1;
memcpy(nt[nowq],nt[q],sizeof(nt[q]));
fa[nowq]=fa[q];
fa[nowp]=fa[q]=nowq;
while(p&&nt[p][c]==q) nt[p][c]=nowq,p=fa[p];
}
}
return nowp;
}
void _count(void)
{
memset(x,0,sizeof(x));
for(int i=1;i<=cnt;i++) x[len[i]]++;
for(int i=1;i<=cnt;i++) x[i]+=x[i-1];
for(int i=1;i<=cnt;i++) y[x[len[i]]--]=i;
}
void creat(void)
{
init();
for(int i=1;i<=n;i++)
{
scanf("%s",str);
a[i]=string(str);
in();
}
int l=1,r=1,pm;
q1[1]=1,q2[1]=1;
while(l<=r)
{
int p=q1[l++];
for(int i=0;i<26;i++)
{
if(t[p][i])
{
pm=_insert(q2[l-1],i);
q1[++r]=t[p][i],q2[r]=pm;
}
}
}
_count();
return ;
}
void get_ans(void)
{
for(int i=1;i<=n;i++)
{
int p=root;
for(int j=0;j<a[i].size();j++)
{
p=nt[p][a[i][j]-'a'];
int np=p;
while(np&&ha[np]!=i) sum[np]++,ha[np]=i,np=fa[np];
}
}
}
void get_f(void)
{
f[root]=0;
for(int i=2;i<=cnt;i++)
f[y[i]]=f[fa[y[i]]]+(sum[y[i]]>=k?len[y[i]]-len[fa[y[i]]]:0);
}
void print_ans(void)
{
get_f();
for(int i=1;i<=n;i++)
{
int ans=0;
int p=root;
for(int j=0;j<a[i].size();j++)
{
p=nt[p][a[i][j]-'a'];
ans+=f[p];
}
printf("%d ",ans);
}
return ;
}
}sam;
int main(void)
{
scanf("%d%d",&sam.n,&sam.k);
sam.creat();
sam.get_ans();
sam.print_ans();
return 0;
}
写法四：我觉得线段树的合并可以代替暴跳fa数组，从而将理论时间复杂度由 nsqrt（n）降低到nlog（n）。
大概是我的理论有问题。。。。
//1008ms
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#include<cstdlib>
#include<string>
#define ll long long
#define llu unsigned ll
using namespace std;
const int maxn=100100;
const int rt=1;
struct Sam
{
int last,cnt,tot;
int n,k;
int nt[maxn<<1][26],fa[maxn<<1];
int len[maxn<<1],sum[maxn<<1];
int x[maxn<<1],y[maxn<<1];
int ha[maxn<<1],f[maxn<<1];
string a[maxn];
char str[maxn];
int root[maxn<<1];
struct node
{
int lc,rc;
int sum;
}t[(maxn<<1)*22];
int newnode(void)
{
int p=++tot;
t[p].lc=t[p].rc=t[p].sum=0;
return p;
}
int in(int p,int l,int r,int id)
{
if(!p) p=newnode();
if(l==r)
{
t[p].sum=1;
return p;
}
int mid=(l+r)>>1;
if(id<=mid) t[p].lc=in(t[p].lc,l,mid,id);
else t[p].rc=in(t[p].rc,mid+1,r,id);
t[p].sum=t[t[p].lc].sum+t[t[p].rc].sum;
return p;
}
int _merge(int p,int q,int l,int r)
{
if(!p) return q;
if(!q) return p;
int now=newnode();
if(l==r)
{
t[now].sum=(t[p].sum+t[q].sum)>0?1:0;
return now;
}
int mid=(l+r)>>1;
t[now].lc=_merge(t[p].lc,t[q].lc,l,mid);
t[now].rc=_merge(t[p].rc,t[q].rc,mid+1,r);
t[now].sum=t[t[now].lc].sum+t[t[now].rc].sum;
return now;
}
void init(void)
{
tot=0;
t[0].lc=t[0].rc=t[0].sum=0;
last=rt;
cnt=1;
fa[1]=0;
len[1]=0;
}
void _insert(int c)
{
if(nt[last][c])
{
int p=last,q=nt[p][c];
if(len[q]==len[p]+1) last=q;
else
{
int nowq=++cnt;
len[nowq]=len[p]+1;
memcpy(nt[nowq],nt[q],sizeof(nt[q]));
fa[nowq]=fa[q];
fa[q]=nowq;
while(p&&nt[p][c]==q) nt[p][c]=nowq,p=fa[p];
last=nowq;
}
}
else
{
int nowp=++cnt,p=last;
len[nowp]=len[last]+1;
while(p&&!nt[p][c]) nt[p][c]=nowp,p=fa[p];
if(!p) fa[nowp]=rt;
else
{
int q=nt[p][c];
if(len[q]==len[p]+1) fa[nowp]=q;
else
{
int nowq=++cnt;
len[nowq]=len[p]+1;
memcpy(nt[nowq],nt[q],sizeof(nt[q]));
fa[nowq]=fa[q];
fa[nowp]=fa[q]=nowq;
while(p&&nt[p][c]==q) nt[p][c]=nowq,p=fa[p];
}
}
last=nowp;
}
return ;
}
void _count(void)
{
memset(x,0,sizeof(x));
for(int i=1;i<=cnt;i++) x[len[i]]++;
for(int i=1;i<=cnt;i++) x[i]+=x[i-1];
for(int i=1;i<=cnt;i++) y[x[len[i]]--]=i;
}
void creat(void)
{
init();
for(int i=1;i<=n;i++)
{
scanf("%s",str);
a[i]=string(str);
last=rt;
int len=strlen(str);
for(int j=0;j<len;j++)
_insert(str[j]-'a');
}
_count();
return ;
}
void get_ans(void)
{
for(int i=1;i<=n;i++)
{
int p=rt;
for(int j=0;j<a[i].size();j++)
{
p=nt[p][a[i][j]-'a'];
root[p]=in(root[p],1,n,i);
}
}
for(int i=cnt;i>=2;i--)
{
sum[y[i]]=t[root[y[i]]].sum;
root[fa[y[i]]]=_merge(root[fa[y[i]]],root[y[i]],1,n);
}
}
void get_f(void)
{
f[rt]=0;
for(int i=2;i<=cnt;i++)
f[y[i]]=f[fa[y[i]]]+(sum[y[i]]>=k?len[y[i]]-len[fa[y[i]]]:0);
}
void print_ans(void)
{
get_f();
for(int i=1;i<=n;i++)
{
int ans=0;
int p=rt;
for(int j=0;j<a[i].size();j++)
{
p=nt[p][a[i][j]-'a'];
ans+=f[p];
}
printf("%d ",ans);
}
return ;
}
}sam;
int main(void)
{
scanf("%d%d",&sam.n,&sam.k);
sam.creat();
sam.get_ans();
sam.print_ans();
return 0;
}
我就说嘛，这次的线段树合并只查询一次，又不用担心再次访问到某个点时，这个点已在其他的线段树中被修改。所以直接合并就好啦（一开始WA是忘了返回值了。）
//928ms
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#include<cstdlib>
#include<string>
#define ll long long
#define llu unsigned ll
using namespace std;
const int maxn=100100;
const int rt=1;
struct Sam
{
int last,cnt,tot;
int n,k;
int nt[maxn<<1][26],fa[maxn<<1];
int len[maxn<<1],sum[maxn<<1];
int x[maxn<<1],y[maxn<<1];
int ha[maxn<<1],f[maxn<<1];
string a[maxn];
char str[maxn];
int root[maxn<<1];
struct node
{
int lc,rc;
int sum;
}t[(maxn<<1)*22];
int newnode(void)
{
int p=++tot;
t[p].lc=t[p].rc=t[p].sum=0;
return p;
}
int in(int p,int l,int r,int id)
{
if(!p) p=newnode();
if(l==r)
{
t[p].sum=1;
return p;
}
int mid=(l+r)>>1;
if(id<=mid) t[p].lc=in(t[p].lc,l,mid,id);
else t[p].rc=in(t[p].rc,mid+1,r,id);
t[p].sum=t[t[p].lc].sum+t[t[p].rc].sum;
return p;
}
int _merge(int p,int q,int l,int r)
{
if(!p) return q;
if(!q) return p;
if(l==r)
{
t[p].sum=(t[p].sum+t[q].sum)>0?1:0;
return p;
}
int mid=(l+r)>>1;
t[p].lc=_merge(t[p].lc,t[q].lc,l,mid);
t[p].rc=_merge(t[p].rc,t[q].rc,mid+1,r);
t[p].sum=t[t[p].lc].sum+t[t[p].rc].sum;
return p;
}
void init(void)
{
tot=0;
t[0].lc=t[0].rc=t[0].sum=0;
last=rt;
cnt=1;
fa[1]=0;
len[1]=0;
}
void _insert(int c)
{
if(nt[last][c])
{
int p=last,q=nt[p][c];
if(len[q]==len[p]+1) last=q;
else
{
int nowq=++cnt;
len[nowq]=len[p]+1;
memcpy(nt[nowq],nt[q],sizeof(nt[q]));
fa[nowq]=fa[q];
fa[q]=nowq;
while(p&&nt[p][c]==q) nt[p][c]=nowq,p=fa[p];
last=nowq;
}
}
else
{
int nowp=++cnt,p=last;
len[nowp]=len[last]+1;
while(p&&!nt[p][c]) nt[p][c]=nowp,p=fa[p];
if(!p) fa[nowp]=rt;
else
{
int q=nt[p][c];
if(len[q]==len[p]+1) fa[nowp]=q;
else
{
int nowq=++cnt;
len[nowq]=len[p]+1;
memcpy(nt[nowq],nt[q],sizeof(nt[q]));
fa[nowq]=fa[q];
fa[nowp]=fa[q]=nowq;
while(p&&nt[p][c]==q) nt[p][c]=nowq,p=fa[p];
}
}
last=nowp;
}
return ;
}
void _count(void)
{
memset(x,0,sizeof(x));
for(int i=1;i<=cnt;i++) x[len[i]]++;
for(int i=1;i<=cnt;i++) x[i]+=x[i-1];
for(int i=1;i<=cnt;i++) y[x[len[i]]--]=i;
}
void creat(void)
{
init();
for(int i=1;i<=n;i++)
{
scanf("%s",str);
a[i]=string(str);
last=rt;
int len=strlen(str);
for(int j=0;j<len;j++)
_insert(str[j]-'a');
}
_count();
return ;
}
void get_ans(void)
{
for(int i=1;i<=n;i++)
{
int p=rt;
for(int j=0;j<a[i].size();j++)
{
p=nt[p][a[i][j]-'a'];
root[p]=in(root[p],1,n,i);
}
}
for(int i=cnt;i>=2;i--)
{
sum[y[i]]=t[root[y[i]]].sum;
root[fa[y[i]]]=_merge(root[fa[y[i]]],root[y[i]],1,n);
}
}
void get_f(void)
{
f[rt]=0;
for(int i=2;i<=cnt;i++)
f[y[i]]=f[fa[y[i]]]+(sum[y[i]]>=k?len[y[i]]-len[fa[y[i]]]:0);
}
void print_ans(void)
{
get_f();
for(int i=1;i<=n;i++)
{
int ans=0;
int p=rt;
for(int j=0;j<a[i].size();j++)
{
p=nt[p][a[i][j]-'a'];
ans+=f[p];
}
printf("%d ",ans);
}
return ;
}
}sam;
int main(void)
{
scanf("%d%d",&sam.n,&sam.k);
sam.creat();
sam.get_ans();
sam.print_ans();
return 0;
}
京公网安备 11010502036488号