uva11107 后缀数组

题意给了n个串 然后计算 这些串中的子串在大于1/2的串中出现 求出这个串的最长长度。 将这些串用一个每出现的不同的字符拼起来 ，然后二分找lcp

#include <iostream>

#include <algorithm>

#include <string.h>

#include <algorithm>

#include <vector>

#include <cstdio>

using namespace std;

const int maxn=;

const int maxm=;

const int MM=maxn*maxm;

struct SuffixArray

{

  int s[MM];      // 原始字符数组（最后一个字符应必须是0，而前面的字符必须非0）

  int sa[MM];     // 后缀数组

  int rank[MM];   // 名次数组. rank[0]一定是n-1，即最后一个字符

  int height[MM]; // height数组

  int t[MM], t2[MM], c[MM]; // 辅助数组

  int n; // 字符个数

     void clear(){ n=; }

  void build(int m)

  {

      int *x=t,*y=t2,i;

      for(i=; i<m; i++)c[i]=;

      for(i=; i<n; i++)c[ x[i] = s[i] ]++;

      for(i=; i<m; i++)c[ i ] += c[ i- ];

     for(i = n-; i >= ; i--) sa[--c[x[i]]] = i;

      for(int k=; k<=n; k<<=)

      {

           int p=;

           for(i=n-k; i<n; i++)y[p++]=i;

           for(i=; i<n; i++)if(sa[i]>=k)y[p++]=sa[i]-k;

           for(i=; i<m; i++)c[i]=;

           for(i=; i<n; i++)c[  x[y[ i] ] ]++;

           for(i=; i<m; i++)c[i]+=c[i-];

           for(i =n-; i>=; i--)sa[  --c[ x[ y[i] ]  ]  ] = y[i];

           swap(x,y);

           p=;

           x[ sa[] ] =;

           for( i=; i<n; i++) x[ sa[i] ]= y[ sa[i] ]==y[sa[i-]] && y[ sa[i]+k ]== y[ sa[i-] +k ]?p-:p++;

           if(p>=n)break;

           m=p;

      }

  }

   void build_height() {

    int i,  k = ;

    for(i = ; i < n; i++) rank[sa[i]] = i;

    height[]=;

    for(i = ; i < n; i++) {

      if(k) k--;

      if(rank[i]==)continue;

      int j = sa[rank[i]-];

      while(i+k<n&&j+k<n&&s[i+k] == s[j+k]) k++;

      height[rank[i]] = k;

    }

  }

}sa;

char word[MM];

int idx[MM],n,maxlen;

int flag[];

void add(int ch, int i)

{

  idx[sa.n] = i;

  sa.s[sa.n++] = ch;

}

// 子串[L,R) 是否符合要求

bool good(int L, int R,int &ss)

{

  if(R - L <= n/) return false;

  int cnt = ;

  for(int i = L; i < R; i++) {

    int x = idx[sa.sa[i]];

    if(x != n && flag[x]!=ss) { flag[x] = ss; cnt++; }

  }

  return cnt > n/;

}

void print_sub(int L, int R)

{

  for(int i = L; i < R; i++)

    printf("%c", sa.s[i] -  + 'a');

  printf("\n");

}

int ss;

bool print_solutions(int len, bool print)

{

  int L = ;

ss++;

  for(int R = ; R <= sa.n; R++) {

    if(R == sa.n || sa.height[R] < len) { // 新开一段

      if(good(L, R,ss)) {

        if(print) print_sub(sa.sa[L], sa.sa[L] + len); else return true;

      }

      ss++;

      L = R;

    }

  }

  return false;

}

void solve(int maxlen)

{

  if(!print_solutions(, false))

    printf("?\n");

  else {

    int L = , R = maxlen, M;

    while(L < R) {

      M = L + (R-L+)/;

      if(print_solutions(M, false)) L = M;

      else R = M-;

    }

    print_solutions(L, true);

  }

}

int main()

{

    int kase=;

    while(scanf("%d",&n)==)

        {

             if(n==)break;

             if(kase++>) puts("");

               maxlen=;

              sa.clear();

              for(int i=; i<n; i++)

                {

                    scanf("%s",word);

                    int sz= strlen(word);

                    maxlen=max(sz,maxlen);

                    for(int j=; j<sz; j++)

                        {

                            add(word[j]-'a'+,i);

                        }

                    add(+i,n);

                }

                add(+n,n);

                if(n==)printf("%s\n",word);

                else

                    {

                        ss=;

                        memset(flag,,sizeof(flag));

                        sa.build( +n+ );

                        sa.build_height();

                        solve(maxlen);

                    }

        }

    return ;

}