POJ_1226

    这个题目可以枚举长度最小的字符串的所有子串，然后暴搜。但为了练一练后缀数组，所以就用后缀数组写了。

#include
     
       #include
      
        #define MAXD 20100 char b[110]; int N, M, h[110], f[MAXD], r[MAXD], rank[MAXD], sa[MAXD], height[MAXD], ws[MAXD], wv[MAXD], wa[MAXD], wb[MAXD]; void init() {
   int i, j, k, x = 128;     k = 0; for(i = 0; i < N; i ++)     {
           scanf("%s", b); for(j = 0; b[j]; j ++)         {
               r[k] = b[j];             f[k] = i;             ++ k;         }         r[k ++] = x ++; for(-- j; j >= 0; j --)         {
               r[k] = b[j];             f[k] = i;             ++ k;         }         r[k ++] = x ++;     }     M = k - 1;     r[M] = 0; } int cmp(int *p, int x, int y, int l) {
   return p[x] == p[y] && p[x + l] == p[y + l]; } void da(int n, int m) {
   int i, j, p, *x = wa, *y = wb, *t; for(i = 0; i < m; i ++)         ws[i] = 0; for(i = 0; i < n; i ++)         ++ ws[x[i] = r[i]]; for(i = 1; i < m; i ++)         ws[i] += ws[i - 1]; for(i = n - 1; i >= 0; i --)         sa[-- ws[x[i]]] = i; for(j = p = 1; p < n; j *= 2, m = p)     {
   for(p = 0, i = n - j; i < n; i ++)             y[p ++] = i; for(i = 0; i < n; i ++) if(sa[i] >= j)                 y[p ++] = sa[i] - j; for(i = 0; i < n; i ++)             wv[i] = x[y[i]]; for(i = 0; i < m; i ++)             ws[i] = 0; for(i = 0; i < n; i ++)             ++ ws[wv[i]]; for(i = 1; i < m; i ++)             ws[i] += ws[i - 1]; for(i = n - 1; i >= 0; i --)             sa[-- ws[wv[i]]] = y[i]; for(t = x, x = y, y = t, x[sa[0]] = 0, i = p = 1; i < n; i ++)             x[sa[i]] = cmp(y, sa[i - 1], sa[i], j) ? p - 1 : p ++;     } } void calheight(int n) {
   int i, j, k = 0; for(i = 1; i <= n; i ++)         rank[sa[i]] = i; for(i = 0; i < n; height[rank[i ++]] = k) for(k ? -- k : 0, j = sa[rank[i] - 1]; r[i + k] == r[j + k]; k ++); } int check(int mid) {
   int i, j, k = 0; for(i = 1; i <= M; i ++)     {
   if(height[i] < mid)         {
   if(k && k == N) return 1;             k = 0;         } else         {
   if(k == 0)             {
                   memset(h, 0, sizeof(h));                 h[f[sa[i - 1]]] = 1;                 ++ k;             } if(!h[f[sa[i]]])             {
                   h[f[sa[i]]] = 1;                 ++ k;             }         }     } return 0; } void solve() {
   int i, j, k, min, max, mid;     da(M + 1, 400);     calheight(M);     min = 0, max = 100; for(;;)     {
           mid = (max + min) / 2; if(mid == min) break; if(check(mid))             min = mid; else             max = mid;     }     printf("%d\n", mid); } int main() {
   int t;     scanf("%d", &t); while(t --)     {
           scanf("%d", &N);         init();         solve();     } return 0; }