codeforces 204e Little Elephant and Strings

codeforces 204e Little Elephant and Strings

​​ The Little Elephant loves strings very much.

He has an array a from n strings, consisting of lowercase English letters. Let’s number the elements of the array from 1 to n, then let’s denote the element number i as ai. For each string ai (1 ≤ i ≤ n) the Little Elephant wants to find the number of pairs of integers l and r (1 ≤ l ≤ r ≤ |ai|) such that substring ai[l… r] is a substring to at least k strings from array a (including the i-th string).

Help the Little Elephant solve this problem.

If you are not familiar with the basic notation in string problems, you can find the corresponding definitions in the notes. Input

The first line contains two space-separated integers — n and k (1 ≤ n, k ≤ 105). Next n lines contain array a. The i-th line contains a non-empty string ai, consisting of lowercase English letter. The total length of all strings ai does not exceed 105. Output

On a single line print n space-separated integers — the i-th number is the answer for string ai.

Please, do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier. Examples Input

3 1 abc a ab

Output

6 1 3

Input

7 4 rubik furik abab baba aaabbbababa abababababa zero

Output

1 0 9 9 21 30 0

Note

Let’s assume that you are given string a = a1a2… a|a|, then let’s denote the string’s length as |a| and the string’s i-th character as ai.

A substring a[l… r] (1 ≤ l ≤ r ≤ |a|) of string a is string alal + 1… ar.

String a is a substring of string b, if there exists such pair of integers l and r (1 ≤ l ≤ r ≤ |b|), that b[l… r] = a.

大概是原题bzoj3473N 220000int st[N][20],height[N],rank[N<<1],rank1[N],s[N],L[N],Log[N],n,kk,cnt[N],bl[N>>1],sa[N],count[N],tmp[N];char a[N];inline int lcp(int x,int y){ x++;int t=Log[y-x+1]; return std::min(st[x][t],st[y-(1<>1];inline bool check(int st,int len){ int l1,r1; if (height[st]>1; if (lcp(mid,st)>=len) r=mid-1;else l=mid+1; }l1=l; } if (height[st+1]>1; if(lcp(st,mid)>=len) l=mid+1;else r=mid-1; }r1=r; } return L[r1]>=l1;}int main(){ freopen("cf.in","r",stdin); scanf("%d%d",&n,&kk);int len=0,m=30; for (int i=1;i<=n;++i){ scanf("%s",a+1);int len1=strlen(a+1);data[i].st=len+1; for (int j=len+1;j<=len+len1;++j) s[j]=a[j-len]-'a'+1,bl[j]=i;data[i].ed=len+len1;len+=len1;s[++len]=++m; }int nn=n;n=len; for (int i=1;i<=n;++i) count[s[i]]=1; for (int i=1;i<=m;++i) count[i]+=count[i-1]; for (int i=1;i<=n;++i) rank[i]=count[s[i]];int k=0; for (int p=1;k!=n;p<<=1,m=k){ for (int i=1;i<=m;++i) count[i]=0; for (int i=1;i<=n;++i) count[rank[i+p]]++; for (int i=1;i<=m;++i) count[i]+=count[i-1]; for (int i=n;i>=1;--i) tmp[count[rank[i+p]]--]=i; for (int i=1;i<=m;++i) count[i]=0; for (int i=1;i<=n;++i) count[rank[i]]++; for (int i=1;i<=m;++i) count[i]+=count[i-1]; for (int i=n;i>=1;--i) sa[count[rank[tmp[i]]]--]=tmp[i]; memcpy(rank1,rank,sizeof(rank)>>1); rank[sa[1]]=k=1; for (int i=2;i<=n;++i){ if (rank1[sa[i]]!=rank1[sa[i-1]]||rank1[sa[i]+p]!=rank1[sa[i-1]+p]) ++k; rank[sa[i]]=k; } }k=0; for (int i=1;i<=n;++i){ if (rank[i]==1) continue; k=k==0?0:k-1; while (s[i+k]==s[sa[rank[i]-1]+k]) ++k; height[rank[i]]=k; }Log[0]=-1;for (int i=1;i<=n;++i) Log[i]=Log[i>>1]+1; for (int i=1;i<=n;++i) st[i][0]=height[i]; for (int j=1;j<=Log[n];++j) for (int i=1;i+(1<kk||num==kk&&cnt[bl[sa[p]]]>1){ --cnt[bl[sa[p]]];if (!cnt[bl[sa[p++]]]) num--; } if (num>=kk) L[i]=p;else L[i]=-1; } for (int i=1;i<=nn;++i){ long long ans=0;k=0; for (int j=data[i].st;j<=data[i].ed;++j){ k=k==0?0:k-1; while (j+k<=data[i].ed&&check(rank[j],k+1))++k;ans+=k; } printf("%lld ",ans); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。