Description

给定n个字符串，询问每个字符串有多少子串（不包括空串）是所有n个字符串中至少k个字符串的子串？

Input

第一行两个整数n，k。

接下来n行每行一个字符串。

Output

一行n个整数，第i个整数表示第i个字符串的答案。

Sample Input

3 1

abc

a

ab

Sample Output

6 1 3

HINT

对于 100% 的数据，1<=n，k<=10^5，所有字符串总长不超过10^5，字符串只包含小写字母。

Solution

加分隔符建出后缀数组，考虑每个后缀的所有前缀，这样就能考虑到所有的子串了。

对于每一个后缀，二分前缀的长度，

然后在二分里面再通过二分左右端点加$ST$表确定$lcp$大于等于之前二分前缀长度的后缀排名区间，

最后用主席树查询一下区间颜色个数是否超过k就行了。查询方法参照HH的项链主席树做法。

话说字符串拼接完了长度是$2\times 10^5$不是$10^5$……数组开小真是太真实了。

Code

1 #include
     
        2 #include
      
         3 #include
       
          4 #define N (200009)  5 #define LL long long  6 using namespace std;  7   8 struct Sgt{
   int ls,rs,val;}Segt[N*18];  9 int sgt_num,Root[N],a[N],Next[N]; 10 int n,m=125,c,k; 11 int wa[N],wb[N],wt[N]; 12 int Rank[N],SA[N],Height[N]; 13 int ST[N][18],LOG2[N]; 14 int ID[N],id_num,End[N]; 15 LL Ans[N]; 16 char r[N],s[N]; 17  18 bool cmp(int *y,int a,int b,int k) 19 { 20     int arank1=y[a]; 21     int brank1=y[b]; 22     int arank2=a+k>=n?-1:y[a+k]; 23     int brank2=b+k>=n?-1:y[b+k]; 24     return arank1==brank1 && arank2==brank2; 25 } 26  27 void Build_SA() 28 { 29     int *x=wa,*y=wb; 30     for (int i=0; i
        
         =0; --i) SA[--wt[x[i]]]=i; 34      35     for (int j=1; j<=n; j<<=1) 36     { 37         int p=0; 38         for (int i=n-j; i
         
          =j) y[p++]=SA[i]-j; 40          41         for (int i=0; i
          
           =0; --i) SA[--wt[x[y[i]]]]=y[i]; 45 46 m=1; swap(x,y); x[SA[0]]=0; 47 for (int i=1; i
           
            =n) break; 50 } 51 } 52 53 void Build_Height() 54 { 55 for (int i=0; i
            
             >1]+1; 70 for (int i=0; i
             
              >1; 88 if (x<=mid) Segt[now].ls=Update(Segt[now].ls,l,mid,x); 89 else Segt[now].rs=Update(Segt[now].rs,mid+1,r,x); 90 return now; 91 } 92 93 int Query(int u,int v,int l,int r,int l1,int r1) 94 { 95 if (l>r1 || r
              
               >1; 98 return Query(Segt[u].ls,Segt[v].ls,l,mid,l1,r1)+Query(Segt[u].rs,Segt[v].rs,mid+1,r,l1,r1); 99 }100 101 void Build_CT()102 {103 for (int i=1; i<=c; ++i) Next[i]=n;104 for (int i=n-1; i>=0; --i) a[i+1]=Next[ID[SA[i]]], Next[ID[SA[i]]]=i;105 for (int i=1; i<=n; ++i) Root[i]=Update(Root[i-1],0,n,a[i]);106 }107 108 bool check(int p,int lim)109 {110 int l,r,L,R;111 l=0,r=p-1,L=p;112 while (l<=r)113 {114 int mid=(l+r)>>1,lcp=Query(mid+1,p);115 if (lcp>=lim) L=mid, r=mid-1;116 else l=mid+1;117 }118 l=p+1,r=n-1,R=p;119 while (l<=r)120 {121 int mid=(l+r)>>1,lcp=Query(p+1,mid);122 if (lcp>=lim) R=mid, l=mid+1;123 else r=mid-1;124 }125 return Query(Root[L],Root[R+1],0,n,R+1,n)>=k;126 }127 128 int main()129 {130 scanf("%d%d",&c,&k);131 for (int i=1; i<=c; ++i)132 {133 scanf("%s",s);134 for (int j=0,l=strlen(s); j
               
                >1;147 if (check(i,mid)) ans=mid, l=mid+1;148 else r=mid-1;149 }150 Ans[ID[SA[i]]]+=ans;151 }152 for (int i=1; i<=c; ++i)153 printf("%lld ",Ans[i]);154 }