POJ3294--Life Forms 后缀数组+二分答案 大于k个字符串的最长公共子串

                                                                          Life Forms

Time Limit: 5000MS		Memory Limit: 65536K
Total Submissions: 10800		Accepted: 2967

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

?

题意: n个字符串， 求大于n/2个字符串的最长子串。  如果有多个按字典序输出。

大致思路：首先把所有字符串用不相同的一个字符隔开（用同一个字符隔开wa了好久）， 这里我是用数字来隔开的。
然后依次求sa，lcp。 我们可以二分答案的长度， 对于长度x，我们可以把 后缀进行分组（lcp[i] < x时 隔开）， 然后对于每一组判断有多少个字符串出现，如果大于n/2说明符合。。对于字典序就不用排序了，，因为我们就是按照sa数组来遍历lcp的。。所以直接得到的答案就是字典序从小到大。

#include <set>
#include <map>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const double eps = 1e-8;
const int M = 2e6+10;
int s[M];
int sa[M], tmp[M], rank[M], lcp[M], k, len;
bool cmp(int i, int j)
{
    if (rank[i] != rank[j])
        return rank[i] < rank[j];
    else
    {
        int x = i+k <= len ? rank[i+k] : -1;
        int y = j+k <= len ? rank[j+k] : -1;
        return x < y;
    }
}
void build_sa()
{
    for (int i = 0; i <= len; i++)
    {
        sa[i] = i;
        rank[i] = i < len ? s[i] : -1;
    }
    for (k = 1; k <= len; k *= 2)
    {
        sort (sa, sa+len+1, cmp);
        tmp[sa[0]] = 0;
        for (int i = 1; i <= len; i++)
        {
            tmp[sa[i]] = tmp[sa[i-1]] + (cmp(sa[i-1], sa[i]) ? 1 : 0);
        }
        for (int i = 0; i <= len; i++)
        {
            rank[i] = tmp[i];
        }
    }
}
void Get_Lcp()
{
    for (int i = 0; i < len; i++)
    {
        rank[sa[i]] = i;
    }
    int h = 0;
    lcp[0] = 0;
    for (int i = 0; i <  len; i++)
    {
        int j = sa[rank[i]-1];
        if (h > 0)
            h--;
        for (; i+h < len && j+h < len; h++)
            if (s[i+h] != s[j+h])
                break;
        lcp[rank[i]] = h;
    }
}
int vis[110], pos[M];
int ans[M], tot;
int Stack[M], top;
bool solve (int x, int n)
{
    int minv = inf;
    int cnt = 0;
    bool flag = false;
    for (int i = 0; i <= len+1; i++)
    {
        if (lcp[i] < x)
        {

            if ( cnt+ (!vis[pos[sa[i-1]]]) > n/2 && (minv != inf && minv >= x))
            {
                if (!flag )
                    tot = 0;
                flag = true;
                ans[tot++] = sa[i-1];
            }
            minv = inf;
            cnt = 0;
            memset(vis, 0, sizeof (vis));
            continue;
        }
        if ( vis[pos[sa[i-1]]]==0)
        {
            cnt++;

        }
        vis[pos[sa[i-1]]] = 1;
        minv = min(minv, lcp[i]);

    }
    return tot > 0 && flag;
}
int string_len[110], c1;
void init()
{
    c1 = tot = 0;
    memset(vis, 0, sizeof (vis));
    memset(string_len, 0, sizeof (string_len));
}
char cacaca[1100];
int main()
{
#ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
   // freopen("wa.txt","w",stdout);
#endif
    int n, cas = 1;
    while ( scanf ("%d", &n), n)
    {
        if (cas != 1)
            printf("
");
        cas++;
        init();
        len = 0;
        int del = 1;
        for (int i = 0; i < n; i++)
        {
            scanf ("%s", cacaca);
            int sub_len = strlen(cacaca);
            for (int j = 0; j < sub_len; j++)
            {
                s[len++] = cacaca[j];
            }
            s[len++] = M+del;
            del++;
            string_len[c1] = sub_len + string_len[c1-1];
            if (c1)
                string_len[c1]++;
            c1++;
        }
        if (n == 1)
        {
            for (int i = 0; i < len-1; i++)
            {
                printf("%c", s[i]);
            }
            continue;
        }
        for (int i = 0, j = 0; i < len; i++)
        {
            if (i >= string_len[j])
            {
                pos[i] = -1;
                j++;
                continue;
            }
            pos[i] = j+1;
        }
        build_sa();
        Get_Lcp();

        int ua = 0, ub = M;
        while (ua + 1 < ub)
        {
            int mid = (ua + ub) >> 1;
            if (mid&&solve(mid, n) == true)
            {

                ua = mid;
            }
            else
                ub = mid;
        }
        if (tot == 0)
            printf("?
");
        else
        {
            if (ua == 0)
            {
                printf("?
");
                continue;
            }
            for (int i = 0; i < tot; i++)
            {
                for (int j = ans[i]; j < ans[i]+ua; j++)
                {
                    printf("%c", s[j]);
                }
                printf("
");
            }
        }
    }
    return 0;
}