uva 11107

花了一个半小时的时间，终于把这个题目给A了；
知道用后缀数组后，这个题目其实不难；
就一个二分；
用白书当模板其实还挺不错的！
  1 #include<cstdio>
  2 #include<cstring>
  3 #include<algorithm>
  4 #define maxn 110009
  5 using namespace std;
  6 
  7 int s[maxn];
  8 int sa[maxn],t[maxn],t2[maxn],c[maxn],n;
  9 
 10 void build_sa(int m)
 11 {
 12     int *x=t,*y=t2;
 13     for(int i=0; i<m; i++)c[i]=0;
 14     for(int i=0; i<n; i++)c[x[i]=s[i]]++;
 15     for(int i=1; i<m; i++)c[i]+=c[i-1];
 16     for(int i=n-1; i>=0; i--)sa[--c[x[i]]]=i;
 17     for(int k=1; k<=n; k<<=1)
 18     {
 19         int p=0;
 20         for(int i=n-k; i<n; i++)y[p++]=i;
 21         for(int i=0; i<n; i++)if(sa[i]>=k)y[p++]=sa[i]-k;
 22         for(int i=0; i<m; i++)c[i]=0;
 23         for(int i=0; i<n; i++)c[x[y[i]]]++;
 24         for(int i=0; i<m; i++)c[i]+=c[i-1];
 25         for(int i=n-1; i>=0; i--)sa[--c[x[y[i]]]]=y[i];
 26         swap(x,y);
 27         p=1;
 28         x[sa[0]]=0;
 29         for(int i=1; i<n; i++)
 30             x[sa[i]]=y[sa[i-1]]==y[sa[i]]&&y[sa[i-1]+k]==y[sa[i]+k]?p-1:p++;
 31         if(p>=n)break;
 32         m=p;
 33     }
 34 }
 35 
 36 int rank[maxn],height[maxn];
 37 void getheight()
 38 {
 39     int k=0;
 40     for(int i=0; i<n; i++)rank[sa[i]]=i;
 41     for(int i=0; i<n; i++)
 42     {
 43         if(k)k--;
 44         int j=sa[rank[i]-1];
 45         while(s[i+k]==s[j+k])k++;
 46         height[rank[i]]=k;
 47     }
 48 }
 49 
 50 int mm,v[maxn],flag[maxn];
 51 
 52 bool solve(int len,bool label)
 53 {
 54     int j,k;
 55     for(int i=2; i<n; i=j+1)
 56     {
 57         while((height[i]<len)&&(i<n))i++;
 58         if(i>n)break;
 59         memset(v,0,sizeof v);
 60         k=1,v[flag[sa[i-1]]]=1;
 61         for(j=i; height[j]>=len; j++)
 62             if (!v[flag[sa[j]]])
 63             {
 64                 v[flag[sa[j]]]=1;
 65                 k++;
 66             }
 67         if (k>=mm/2+1)
 68         {
 69             if(label)
 70             {
 71                 for(k=sa[i-1]; k<sa[i-1]+len; k++) printf("%c",s[k]);
 72                 printf("
");
 73             }
 74             else return 1;
 75         }
 76     }
 77     return 0;
 78 }
 79 
 80 char tt[1009];
 81 int main()
 82 {
 83     int i,ma=0,mi=0,ca=1;
 84     while(scanf("%d",&mm)&&mm)
 85     {
 86         if(!ca) printf("
");
 87         else ca=0;
 88         memset(sa,0,sizeof sa);
 89         memset(flag,0,sizeof flag);
 90         ma=mi=1;
 91         for(i=1,n=0; i<=mm; i++)
 92         {
 93             scanf("%s",tt);
 94             int l=strlen(tt);
 95             ma=max(ma,l);
 96             for(int j=0; j<l; j++)
 97             {
 98                 s[n]=tt[j];
 99                 flag[n++]=i;
100             }
101             s[n++]=150+i;
102         }
103         s[n++]=0;
104         if(mm==1)
105         {
106             puts(tt);
107             continue;
108         }
109         build_sa(151+mm);
110         getheight();
111         while(mi<=ma)
112         {
113             int mid=(mi+ma)>>1;
114             if(solve(mid,0))mi=mid+1;
115             else ma=mid-1;
116         }
117         if(!ma)puts("?");
118         else solve(ma,1);
119     }
120     return 0;
121 }
View Code