POJ 3294 后缀数组：求不小于k个字符串中的最长子串

思路：先把所有的串连接成一个串，串写串之前用没出现过的字符隔开，然后求后缀；对height数组分组二分求得最长的公共前缀，公共前缀所在的串一定要是不同的，不然就不是所有串的公共前缀了，然后记下下标和长度即可。

刚开始理解错题意，然后不知道怎么写，然后看别人题解也不知道怎么意思，后面看了好久才知道题目意思理解错了。

时间四千多ms，别人才一百多ms，不知道别人怎么做的……

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#include<queue>
#include<set>
#include<cmath>
#include<bitset>
#define mem(a,b) memset(a,b,sizeof(a))
#define lson i<<1,l,mid
#define rson i<<1|1,mid+1,r
#define llson j<<1,l,mid
#define rrson j<<1|1,mid+1,r
#define INF 0x7fffffff
#define maxn 110010
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
void radix(int *str,int *a,int *b,int n,int m)
{
    static int count[maxn];
    mem(count,0);
    for(int i=0; i<n; i++) ++count[str[a[i]]];
    for(int i=1; i<=m; i++) count[i]+=count[i-1];
    for(int i=n-1; i>=0; i--) b[--count[str[a[i]]]]=a[i];
}
void suffix(int *str,int *sa,int n,int m) //倍增算法计算出后缀数组sa
{
    static int rank[maxn],a[maxn],b[maxn];
    for(int i=0; i<n; i++) rank[i]=i;
    radix(str,rank,sa,n,m);
    rank[sa[0]]=0;
    for(int i=1; i<n; i++)
        rank[sa[i]]=rank[sa[i-1]]+(str[sa[i]]!=str[sa[i-1]]);
    for(int i=0; 1<<i<n; i++)
    {
        for(int j=0; j<n; j++)
        {
            a[j]=rank[j]+1;
            b[j]=j+(1<<i)>=n?0:rank[j+(1<<i)]+1;
            sa[j]=j;
        }
        radix(b,sa,rank,n,n);
        radix(a,rank,sa,n,n);
        rank[sa[0]]=0;
        for(int j=1; j<n; j++)
            rank[sa[j]]=rank[sa[j-1]]+(a[sa[j-1]]!=a[sa[j]]||b[sa[j-1]]!=b[sa[j]]);
    }
}
void calcHeight(int *str,int *sa,int *h,int *rank,int n) //求出最长公共前缀数组h
{
    int k=0;
    h[0]=0;
    for(int i=0; i<n; i++) rank[sa[i]]=i;
    for(int i=0; i<n; i++)
    {
        k=k==0?0:k-1;
        if(rank[i])
            while(str[i+k]==str[sa[rank[i]-1]+k]) k++;
        else k=0;
        h[rank[i]]=k;
    }
}
int a[maxn],sa[maxn],height[maxn],rank[maxn];
int v[maxn],vis[1002],r,n,len,j;
char s[1002];
bool judge(int m)
{
    int sum=0;
    mem(vis,0); vis[0]=1;
    if(!vis[v[sa[0]]]) sum++;
    vis[v[sa[0]]]=1;
    for(int i=1;i<len;i++)
    {
        if(height[i]<m) sum=0,mem(vis,0),vis[0]=1;
        if(!vis[v[sa[i]]]) sum++;
        if(sum>n/2) return true;
        vis[v[sa[i]]]=1;
    }
    return false;
}
int binary()
{
    int ans=-1,mid,l=1;
    while(l<=r)
    {
        mid=(l+r)>>1;
        if(judge(mid)) ans=mid,l=mid+1;
        else r=mid-1;
    }
    return ans;
}
void print(int st,int length)
{
    for(int i=st;i<st+length;i++)
        printf("%c",a[i]-5);
    puts("");
}
int main()
{
    //freopen("1.txt","r",stdin);
    bool flag=false;
    while(scanf("%d",&n)&&n)
    {
        if(flag) puts("");
        else flag=true;
        len=r=j=0;
        for(int i=1;i<=n;i++)
        {
            scanf("%s",s);
            int len1=strlen(s);
            if(r<len1) r=len1;//二分上限
            for(int k=0;k<len1;k++)
                a[len+k]=s[k]+5,v[len+k]=i;//v记录在哪个串中
            a[len+len1]=++j;//字符串中间用没出现过的字符隔开
            v[len+len1]=0;
            len=len+len1+1;
        }
        len--;
        if(n==1) printf("%s\n",s);
        else
        {
            suffix(a,sa,len,256);
            calcHeight(a,sa,height,rank,len);
            int length=binary();
            if(length==-1) puts("?");
            else
            {
                int sum=0,i;
                mem(vis,0);
                vis[0]=1;//标记中间间隔的字符已经访问过
                if(!vis[v[sa[0]]]) sum++;
                vis[v[sa[0]]]=1;
                for(i=1;i<len;i++)
                {
                    if(height[i]<length)
                    {
                        if(sum>n/2) print(sa[i-1],length);
                        sum=0,mem(vis,0),vis[0]=1;
                    }
                    if(!vis[v[sa[i]]]) sum++;
                    vis[v[sa[i]]]=1;
                }
                if(sum>n/2) print(sa[i-1],length);
            }
        }
    }
    return 0;
}

POJ 3294 后缀数组：求不小于k个字符串中的最长子串,布布扣,bubuko.com

POJ 3294 后缀数组：求不小于k个字符串中的最长子串

原文：http://blog.csdn.net/u011466175/article/details/38583805