这道题应该是后缀数组的套路题啊，把单词连接起来，中间用没有出现过且互不相同的字符来分隔开，求一下(height)数组。
对于一个单词来说，设单词长(len)，所在的后缀为(i)，如果某后缀(j)满足(lcp(i,j)==len)，则(j)的前缀与这个单词相等。因为和(i)的(lcp)大小是从(i)向两边递减的，所以可以分别从后往前，从前往后两遍单调栈找出左右最远能满足条件的后缀(l,r)，区间大小(l-r+1)就是总数
吐槽一下这题我开始交了两遍R炸了，原因竟是加分隔符的时候加入了一些奇怪的字符...，把(s)改成(int)就好了...
#include<map>
#include<cmath>
#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=2e6+100;
struct SA{
int sa[maxn],tp[maxn],tax[maxn],rk[maxn],h[maxn],n,m,len[300],bj[maxn];
int siz[300],st[maxn],top,tot,s[maxn];
void Qsort(){
for(int i=0;i<=m;i++) tax[i]=0;
for(int i=1;i<=n;i++) tax[rk[i]]++;
for(int i=1;i<=m;i++) tax[i]+=tax[i-1];
for(int i=n;i>=1;i--)
sa[tax[rk[tp[i]]]--]=tp[i];
}
void getsa(){
m=1000;
for(int i=1;i<=n;i++)
rk[i]=s[i],tp[i]=i;
Qsort();
for(int p=1,w=1;p<n;w<<=1,m=p){
p=0;
for(int i=1;i<=w;i++) tp[++p]=n+i-w;
for(int i=1;i<=n;i++) if(sa[i]>w) tp[++p]=sa[i]-w;
Qsort();
swap(tp,rk);
rk[sa[1]]=p=1;
for(int i=2;i<=n;i++)
rk[sa[i]]=tp[sa[i]]==tp[sa[i-1]]&&tp[sa[i]+w]==tp[sa[i-1]+w]?p:++p;
}
}
void geth(){
for(int i=1,j,p=0;i<=n;h[rk[i++]]=p)
for(p?p--:p,j=sa[rk[i]-1];s[j+p]==s[i+p];p++);
}
void ycl(){
h[0]=-0x7fffffff,top=0;
for(int i=1;i<=n;i++){
while(h[st[top]]>=h[i]) top--;
if(bj[sa[i]]&&h[i]==len[bj[sa[i]]])
siz[bj[sa[i]]]=i-st[top];
st[++top]=i;
}
h[n+1]=-0x7fffffff,st[0]=n+1,top=0;
for(int i=n-1;i>=1;i--){
while(h[st[top]]>=h[i+1]) top--;
if(bj[sa[i]]&&h[i+1]==len[bj[sa[i]]]) siz[bj[sa[i]]]+=st[top]-i-1;
st[++top]=i+1;
}
}
}sa;
int n,m;
char a[maxn];
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%s",a+1);
m=strlen(a+1);
sa.bj[sa.n+1]=i;
sa.len[i]=m;
for(int j=1;j<=m;j++)
sa.s[++sa.n]=a[j];
sa.s[++sa.n]='z'+i;
}
sa.getsa(),sa.geth(),sa.ycl();
for(int i=1;i<=n;i++)
printf("%d
",sa.siz[i]+1);
return 0;
}