题目链接：https://cn.vjudge.net/contest/318888#problem/L

 

思路：

 

  1 #include <stdio.h>
  2 #include <iostream>
  3 #include <algorithm>
  4 #include <string.h>
  5 #include <stdlib.h>
  6 #include <math.h>
  7 #include <queue>
  8 #include <set>
  9 
 10 #define INF 0x3f3f3f3f
 11 #define pii pair<int,int>
 12 #define LL long long
 13 using namespace std;
 14 typedef unsigned long long ull;
 15 const int MAXN = 2e5 + 10;
 16 int t;
 17 int wa[MAXN], wb[MAXN], wv[MAXN], ws_[MAXN];
 18 void Suffix(int *r, int *sa, int n, int m)
 19 {
 20     int i, j, k, *x = wa, *y = wb, *t;
 21     for(i = 0; i < m; ++i) ws_[i] = 0;
 22     for(i = 0; i < n; ++i) ws_[x[i] = r[i]]++;
 23     for(i = 1; i < m; ++i) ws_[i] += ws_[i - 1];
 24     for(i = n - 1; i >= 0; --i) sa[--ws_[x[i]]] = i;
 25     for(j = 1, k = 1; k < n; j *= 2, m = k)
 26     {
 27         for(k = 0, i = n - j; i < n; ++i) y[k++] = i;
 28         for(i = 0; i < n; ++i) if(sa[i] >= j) y[k++] = sa[i] - j;
 29         for(i = 0; i < n; ++i) wv[i] = x[y[i]];
 30         for(i = 0; i < m; ++i) ws_[i] = 0;
 31         for(i = 0; i < n; ++i) ws_[wv[i]]++;
 32         for(i = 1; i < m; ++i) ws_[i] += ws_[i - 1];
 33         for(i = n - 1; i >= 0; --i) sa[--ws_[wv[i]]] = y[i];
 34         t = x;
 35         x = y;
 36         y = t;
 37         for(x[sa[0]] = 0, i = k = 1; i < n; ++i)
 38             x[sa[i]] = (y[sa[i - 1]] == y[sa[i]] && y[sa[i - 1] + j] == y[sa[i] + j]) ? k - 1 : k++;
 39     }
 40 }
 41 int Rank[MAXN], height[MAXN], sa[MAXN], r[MAXN];
 42 char s[MAXN];
 43 int indexx[MAXN],vis[MAXN];
 44 void calheight(int *r,int *sa,int n)
 45 {
 46     int i,j,k=0;
 47     for(i=1; i<=n; i++)Rank[sa[i]]=i;
 48     for(i=0; i<n; height[Rank[i++]]=k)
 49         for(k?k--:0,j=sa[Rank[i]-1]; r[i+k]==r[j+k]; k++);
 50 }
 51 
 52 struct Node{
 53     int cnt,maxsa,minsa;
 54     void init(){
 55         cnt = 0;
 56         maxsa = -1;
 57         minsa = MAXN;
 58     }
 59 }node[20];
 60 
 61 bool check(int x,int n){
 62     int tot = 0;
 63     int idx,lidx;
 64     for (int i=0;i<t;i++){
 65         node[i].init();
 66     }
 67     memset(vis,0, sizeof(vis));
 68     for (int i=1;i<n;i++){
 69         idx = indexx[sa[i]],lidx = indexx[sa[i-1]];
 70         if (i == n-1){
 71             for (int k=0;k<t;k++){
 72                 if (node[k].cnt>=2 && node[k].maxsa-node[k].minsa>=x){
 73                     tot++;
 74                 }
 75                 node[k].init();
 76             }
 77             if (tot == t){
 78                 return true;
 79             }
 80             tot = 0;
 81             break;
 82         }
 83         if (height[i]>=x){
 84             if (!vis[i]){
 85                 vis[i] = 1;
 86                 node[idx].cnt++;
 87                 node[idx].maxsa = max(sa[i],node[idx].maxsa);
 88                 node[idx].minsa = min(sa[i],node[idx].minsa);
 89             }
 90             if (!vis[i-1]){
 91                 vis[i-1] = 1;
 92                 node[lidx].cnt++;
 93                 node[lidx].maxsa = max(sa[i-1],node[lidx].maxsa);
 94                 node[lidx].minsa = min(sa[i-1],node[lidx].minsa);
 95             }
 96         }
 97         else{
 98             for (int k=0;k<t;k++){
 99                 if (node[k].cnt>=2 && node[k].maxsa-node[k].minsa>=x){
100                     tot++;
101                 }
102                 node[k].init();
103             }
104             if (tot == t){
105                 return true;
106             }
107             tot = 0;
108         }
109     }
110     return false;
111 }
112 
113 
114 int main()
115 {
116     int T;
117     scanf("%d",&T);
118     while (T--) {
119         scanf("%d",&t);
120         int XX = 30;
121         int n = 0;
122         for (int i=0;i<t;i++){
123             scanf("%s",s);
124             int len = strlen(s);
125             for (int j=0;j<len;j++){
126                 r[n++] = s[j]-'a'+1;
127                 indexx[n-1] = i;
128             }
129             indexx[n] = i;
130             r[n++] = XX++;
131         }
132         r[n] = 0;
133         Suffix(r,sa,n+1,128);
134         calheight(r,sa,n);
135         int L=1,R=10000,mid,len=0;
136         while (L<=R){
137             mid = (L+R)>>1;
138             if (check(mid,n)){
139                 len = mid;
140                 L = mid+1;
141             }else
142                 R = mid-1;
143         }
144         printf("%d\n",len);
145     }
146     return 0;
147 }