poj 3294 Life Forms（后缀数组）

题意：给你最多100个字符串，求最长的且是一半以上的字符串的公共子串，如果有多个，按字典序输出。

思路：先把各个串拼起来，中间加上一个之前未出现过的字符，然后求后缀。然后根据h数组和sa数组，求出最长的公共串。

#include
#include
#include
using std::sort;
#define V 220000
int r[V],sa[V],h[V],a[V],b[V],X[V],Y[V];
int acl[120],len[110],tot,mark[V],mark_len,be[V],m[110],max_len;
char s[V],out1[V],out2[V];
void calh(int n)
{
    int i,j,k=0;
    for(i=1; i<=n; i++)r[sa[i]]=i;
    for(i=0; i=0;i--)sa[--b[x[i]]]=i;
    for(j=1,p=1;p=j)y[p++]=sa[i]-j;
        for(i=0;  i=0;i--)sa[--b[x[y[i]]]]=y[i];
        for(t=x,x=y,y=t,x[sa[0]]=0,i=1,p=1;ih[i])//更新mi
            m[j]=h[i];
        if(h[i]m[be[i]]){
            if(m[be[i]]==0||m[be[i]]m[be[i-1]]){
            if(m[be[i-1]]==0||m[be[i-1]]=cou){
            cur_len=getmin(cou);
            if(cur_len>max_len)
            {
                mark_len=1;
                mark[0]=sa[i];
                max_len=cur_len;
            }
            else if(cur_len==max_len)
                mark[mark_len++]=sa[i];
        }
    }
}
int main()
{
    int i,j,k,t,n;
    for(i=1;i<=96;i++)acl[i]=i;
    for(i=97;i<=110;i++)acl[i]=i+26;
    while(scanf("%d",&t)!=-1&&t)
    {
       len[0]=-1;
       for(i=1;i<=t;i++)
       {
          scanf("%s",s+len[i-1]+1);
          len[i]=strlen(s);
          s[len[i]]=acl[i];
       }
       s[len[t]]=0;
       n=strlen(s);
       for(i=0;i