程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> poj3294 UVA 11107 Life Forms 後綴數組

poj3294 UVA 11107 Life Forms 後綴數組

編輯：C++入門知識

poj3294 UVA 11107 Life Forms 後綴數組

http://poj.org/problem?id=3294

Life Forms Time Limit: 5000MS Memory Limit: 65536K Total Submissions: 9931 Accepted: 2739

Description

You may have wondered why most extraterrestrial life forms resemble humans, differing by superficial traits such as height, colour, wrinkles, ears, eyebrows and the like. A few bear no human resemblance; these typically have geometric or amorphous shapes like cubes, oil slicks or clouds of dust.

The answer is given in the 146th episode of Star Trek - The Next Generation, titled The Chase. It turns out that in the vast majority of the quadrant's life forms ended up with a large fragment of common DNA.

Given the DNA sequences of several life forms represented as strings of letters, you are to find the longest substring that is shared by more than half of them.

Input

Standard input contains several test cases. Each test case begins with 1 ≤ n ≤ 100, the number of life forms. n lines follow; each contains a string of lower case letters representing the DNA sequence of a life form. Each DNA sequence contains at least one and not more than 1000 letters. A line containing 0 follows the last test case.

Output

For each test case, output the longest string or strings shared by more than half of the life forms. If there are many, output all of them in alphabetical order. If there is no solution with at least one letter, output "?". Leave an empty line between test cases.

Sample Input

3
abcdefg
bcdefgh
cdefghi
3
xxx
yyy
zzz
0

Sample Output

bcdefg
cdefgh

?

Source

Waterloo Local Contest, 2006.9.30

題意：求一個長度最大的字符串，使其在超過一半的給定字符串中出現，存在多個按字典序輸出。

思路：用不同的分隔符把給定字符串拼起來。然後我們二分答案，掃描height數組，判斷長度為p的串是否連續超過一半串中連續出現，注意這裡並不是連續n/2個連續height數組裡的，而是屬於不同給定字符串的n/2個，所以可以開始預處理每一個後綴屬於哪個字符串。最後輸出和判斷一樣，按照字典序由於是掃描height數組所以保證了。

RE了好多發，發現是這個問題，在分隔字符串時，s[n]='z'+i,a[n]=s[n]-'a'+i+1;這樣寫會出問題233，a[n]賦'z'-'a'+1+i就好了。

poj用set判斷會超時。。

/**
 * @author neko01
 */
//#pragma comment(linker, "/STACK:102400000,102400000")
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long LL;
#define min3(a,b,c) min(a,min(b,c))
#define max3(a,b,c) max(a,max(b,c))
#define pb push_back
#define mp(a,b) make_pair(a,b)
#define clr(a) memset(a,0,sizeof a)
#define clr1(a) memset(a,-1,sizeof a)
#define dbg(a) printf("%d\n",a)
typedef pair pp;
const double eps=1e-9;
const double pi=acos(-1.0);
const int N=101005;
int sa[N]; //排第幾的是哪個後綴
//sa[1~n]為有效值，sa[0]必定為n是無效值
int rank[N]; //rank後綴i排第幾
//rank[0~n-1]為有效值，rank[n]必定為0無效值
int height[N]; //sa[i]和sa[i-1]的最長公共前綴
//height[2~n]為有效值
int t1[N],t2[N],c[N];
void build_sa(int s[],int n,int m)
{
    int *x=t1,*y=t2;
    //第一輪計數排序
    for(int i=0;i=0;i--) sa[--c[x[i]]]=i;
    for(int j=1;j<=n;j<<=1)
    {
        int p=0;
        //直接利用sa數組排序第二關鍵字
        for(int i=n-j;i=j) y[p++]=sa[i]-j;
        //計數排序第一關鍵字
        for(int i=0;i=0;i--) sa[--c[x[y[i]]]]=y[i];
        //根據sa和x數組計算新的x數組
        swap(x,y);
        p=1,x[sa[0]]=0;
        for(int i=1;i=n) break;
        m=p;
    }
}
void getheight(int s[],int n)
{
    int k=0;
    for(int i=0;i<=n;i++)
        rank[sa[i]]=i;
    for(int i=0;ist;
    //st.insert(id[sa[1]]);
    clr(vis);
    int sz=0;
    vis[id[sa[1]]]=true;
    sz++;
    for(int i=2;i<=n;i++)
    {
        while(i<=n&&height[i]>=x) //st.insert(id[sa[i]]),i++;
        {
            if(!vis[id[sa[i]]])
            {
                vis[id[sa[i]]]=true;
                sz++;
            }
            i++;
        }
        //if(st.size()>m/2)
        if(sz>m/2)
        {
            if(flag==0) return true;
            for(int j=0;j>1;
            if(gao(n,mid,t,0))
                ans=mid,l=mid+1;
            else r=mid-1;
        }
        if(ans==-1) puts("?");
        else gao(n,ans,t,1);
    }
    return 0;
}