題目分析：
用"$"連接配接字尾數組，然後做一個主席樹求區間内不同的數的個數。二分一個字首長度再在主席樹上求不同的數的個數。
代碼:
1 #include<bits/stdc++.h>
2 using namespace std;
3
4 const int maxn = 132000;
5 const int N = 130000;
6
7 int m,n,k;
8 string hmk[maxn],str;
9 int sum[maxn];
10
11 int sa[maxn],rk[maxn],X[maxn],Y[maxn];
12 int height[maxn],h[maxn],RMQ[maxn][20],Tnum;
13 long long ans[maxn];
14
15 struct node{
16 int ch[2],sum;
17 }CMT[maxn*35];
18
19 int chk(int x,int k){
20 return rk[sa[x]]==rk[sa[x-1]]&&rk[sa[x]+(1<<k)]==rk[sa[x-1]+(1<<k)];
21 }
22
23 void getsa(){
24 for(int i=0;i<n;i++) X[str[i]]++;
25 for(int i=1;i<=N;i++) X[i] += X[i-1];
26 for(int i=n-1;i>=0;i--) sa[X[str[i]]--] = i;
27 for(int i = 2, num = 1;i <= n;i++)
28 rk[sa[i]] = (str[sa[i]] == str[sa[i-1]]?num:++num);
29 rk[sa[1]] = 1;
30 for(int k=1;(1<<k-1)<=n;k++){
31 for(int i=1;i<=N;i++) X[i] = 0;
32 for(int i=n-(1<<k-1);i<n;i++) Y[i-n+(1<<k-1)+1]=i;
33 for(int i=1,j=(1<<k-1)+1;i<=n;i++)
34 if(sa[i]>=(1<<k-1))Y[j++]=sa[i]-(1<<k-1);
35 for(int i=0;i<n;i++) X[rk[i]]++;
36 for(int i=1;i<=N;i++) X[i]+=X[i-1];
37 for(int i=n;i>=1;i--) sa[X[rk[Y[i]]]--] = Y[i];
38 int num = 1; Y[sa[1]] = 1;
39 for(int i=2;i<=n;i++) Y[sa[i]] = (chk(i,k-1)?num:++num);
40 for(int i=0;i<n;i++) rk[i] = Y[i];
41 if(num == n) break;
42 }
43 }
44 void getheight(){
45 for(int i=0;i<n;i++){
46 if(i) h[i] = max(0,h[i-1]-1); else h[i] = 0;
47 if(rk[i] == 1) continue;
48 int comp = sa[rk[i]-1];
49 while(str[comp+h[i]] == str[i+h[i]])h[i]++;
50 }
51 for(int i=0;i<n;i++) height[rk[i]] = h[i];
52 for(int i=1;i<=n;i++) RMQ[i][0] = height[i];
53 for(int k=1;(1<<k)<=n;k++){
54 for(int i=1;i<=n;i++){
55 if(i+(1<<k-1)>n) RMQ[i][k]=RMQ[i][k-1];
56 else RMQ[i][k] = min(RMQ[i][k-1],RMQ[i+(1<<k-1)][k-1]);
57 }
58 }
59 }
60
61 int pww[maxn];
62 int getLCP(int L,int R){
63 if(L == R) return n-sa[L];
64 L++;
65 int k = pww[R-L+1];
66 return min(RMQ[L][k],RMQ[R-(1<<k)+1][k]);
67 }
68
69 void build_empty_tree(int now,int tl,int tr){
70 if(tl == tr) return;
71 int mid = (tl+tr)/2;
72 Tnum++; CMT[now].ch[0] = Tnum;
73 build_empty_tree(Tnum,tl,mid);
74 Tnum++; CMT[now].ch[1] = Tnum;
75 build_empty_tree(Tnum,mid+1,tr);
76 }
77
78 void Modify(int lst,int now,int tl,int tr,int pos,int dt){
79 CMT[now] = CMT[lst];
80 if(tl == tr){CMT[now].sum += dt;}
81 else{
82 int mid = (tl+tr)/2;
83 if(pos <= mid){
84 CMT[now].ch[0] = ++Tnum;
85 Modify(CMT[lst].ch[0],Tnum,tl,mid,pos,dt);
86 }else{
87 CMT[now].ch[1] = ++Tnum;
88 Modify(CMT[lst].ch[1],Tnum,mid+1,tr,pos,dt);
89 }
90 CMT[now].sum += dt;
91 }
92 }
93
94 int imp[maxn],his[maxn];
95 void build_CMT(){
96 his[0] = 1;
97 for(int i=1;i<=n;i++){
98 if(imp[sum[sa[i]]]){
99 int z = ++Tnum;
100 Modify(his[i-1],z,1,n,imp[sum[sa[i]]],-1);
101 his[i] = ++Tnum; imp[sum[sa[i]]] = i;
102 Modify(z,his[i],1,n,i,1);
103 }else{
104 his[i] = ++Tnum; imp[sum[sa[i]]] = i;
105 Modify(his[i-1],his[i],1,n,i,1);
106 }
107 }
108 }
109
110 int query(int now,int tl,int tr,int l,int r){
111 if(tl >= l && tr <= r) return CMT[now].sum;
112 if(tl > r || tr < l) return 0;
113 int mid = (tl+tr)/2;
114 int as=query(CMT[now].ch[0],tl,mid,l,r)+query(CMT[now].ch[1],mid+1,tr,l,r);
115 return as;
116 }
117
118 int rgt[maxn];
119 void work(){
120 getsa();
121 getheight();
122 sum[n] = 1;rgt[n] = n;
123 for(int i=n-1;i>=0;i--){
124 sum[i] = sum[i+1]+(str[i] == '$');
125 if(str[i] == '$') rgt[i] = i;
126 else rgt[i] = rgt[i+1];
127 }
128 Tnum = 1;
129 build_empty_tree(1,1,n);
130 build_CMT();
131 for(int i=m;i<=n;i++){
132 int l = 0,r = rgt[sa[i]]-sa[i];
133 while(l < r){
134 int mid = (l+r+1)/2;
135 int al = 1,ar = i;
136 while(al < ar){
137 int midd = (al+ar)/2;
138 if(getLCP(midd,i) >= mid) ar = midd;
139 else al = midd+1;
140 }
141 int tl = i,tr = n;
142 while(tl < tr){
143 int midd = (tl+tr+1)/2;
144 if(getLCP(i,midd) >= mid) tl = midd;
145 else tr = midd-1;
146 }
147 int mmp = query(his[tl],1,n,al,tl);
148 if(mmp >= k) l = mid;
149 else r = mid-1;
150 }
151 ans[m-sum[sa[i]]+1] += l;
152 }
153 for(int i=1;i<=m;i++) printf("%lld ",ans[i]);
154 }
155
156 int main(){
157 ios::sync_with_stdio(false);
158 cin.tie(0);
159 cin >> m >> k;
160 for(int i=1;i<=m;i++) cin >> hmk[i];
161 for(int i=1;i<m;i++) str += hmk[i],str += '$';
162 str += hmk[m];
163 n = str.length();
164 pww[1] = 0;
165 for(int i=2;i<=n;i++) pww[i] = pww[i/2]+1;
166 work();
167 return 0;
168 } 轉載于:https://www.cnblogs.com/Menhera/p/10102070.html