UVa 11107 生命的形式（不小于k个字符串中的最长子串）

题意：
给定n个字符串，求出现在不小于n的一半个字符串的最长子串，如果有多个，则按字典序输出。

思路：

首先就是将这n个字符串连接起来，然后二分答案，每次只需要判断是否有一个长度为p的串在超过一半的串中连续出现，判断方法是扫描一遍height数组，把它分成若干段，每当height[i]小于p时开辟一个新段，则每一段的最初p个字符均相同。只要某一段中包含了超过n/2个原串的后缀，p就是满足条件的。

 #include<iostream>

 #include<algorithm>

 #include<cstring>

 #include<cstdio>

 #include<vector>

 #include<stack>

 #include<queue>

 #include<cmath>

 #include<map>

 #include<set>

 using namespace std;

 typedef long long ll;

 typedef pair<int,int> pll;

 const int INF = 0x3f3f3f3f;

 const int maxn = +;

 int n,k;

 int s[maxn];

 bool vis[];

 int start[maxn];

 int belong[maxn];

 int sa[maxn],t[maxn],t2[maxn],c[maxn];

 int Rank[maxn],height[maxn];

 void build_sa(int m)

 {

     int *x=t,*y=t2;

     //基数排序

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

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

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

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

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

     {

         int p=;

         //直接利用sa数组排序第二关键字

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

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

         //基数排序第一关键字

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

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

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

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

         //根据sa和y计算新的x数组

         swap(x,y);

         p=;

         x[sa[]]=;

         for(int 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 getHeight(int n)

 {

     int i,j,k=;

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

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

     {

         if(k)  k--;

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

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

         height[Rank[i]]=k;

     }

 }

 bool judge(int n, int len, int num)

 {

     int size=;

     int cnt = ;

     memset(vis,,sizeof(vis));

     cnt++;

     vis[belong[sa[]]] = ;

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

     {

         if(height[i] < len)

         {

             if(cnt>=num)  start[++size]=sa[i-];  //可行，保存好起点

             memset(vis,,sizeof(vis));

             vis[belong[sa[i]]] = ;

             cnt=;

         }

         else

             if(!vis[belong[sa[i]]])

             {

                 cnt++;

                 vis[belong[sa[i]]] = ;

             }

     }

     if(cnt>=num)  start[++size]=sa[n-];  //这儿需要注意，不要忽略了最后一段

     if(size)

     {

         start[]=size;

         return ;

     }

     return ;

 }

 char str[];

 int main()

 {

     //freopen("in.txt","r",stdin);

     bool flag=true;

     while(~scanf("%d",&k) && k)

     {

         if(!flag) printf("\n");

         else flag = false;

         int pos=,cas=;

         int l=,r=;

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

         {

             scanf("%s",str);

             int len=strlen(str);

             r=max(r,len);

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

             {

                 s[pos+j]=(int)str[j]+;

                 belong[pos+j] = i;

             }

             s[pos+len]=cas++;

             pos=pos+len+;

         }

         s[pos]=;

         n=pos;

         build_sa();

         getHeight(n-);

         int ans=;

         while(l <= r)

         {

             int mid = (l+r) >> ;

             if(judge(pos,mid,k/+))

             {

                 ans = mid;

                 l = mid + ;

             }

             else r = mid - ;

         }

         if(ans == ) printf("?\n");

         else

         {

             for(int i=;i<=start[];i++)

             {

                 for(int j=start[i];j<start[i]+ans;j++)

                     printf("%c",s[j]-);

                 printf("\n");

             }

         }

     }

     return ;

 }