学步园

这道题算是后缀数组的经典应用了：求出一个子串，使得其在超过一半的字符串中出现过。

和以往的做法类似：用不同的分隔符把所有的字符串分隔开并组成一个字符串，然后求出height数组，再二分答案，对于某一个可能的解在对height数组分组的时候要注意我们需要确定该段的所有后缀来自于一半以上的字符串而不是单纯的计算区间的长度。所以在把一个后缀加进一个分组的时候同时要记录该后缀首字符所属的那个字符串的也出现了，这里我用了数组h[i]表示后缀i的首字符所属的字符串编号，同时用数组flag[i]表示编号为i的字符串在该分组中是否出现过，每次分组结束后统计出现的字符串的个数，来判断该分组是否满足要求。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int MAXN = 200000;
int r[MAXN];
int sa[MAXN], t[MAXN], t2[MAXN], c[MAXN];
int rank[MAXN], height[MAXN];
int n, len;
char str[105][1005];
int h[MAXN], flag[105];

void build_sa(int * s, int n, int m)
{
    int i, * x = t, * y = t2;
    for(i = 0; i < m; ++i) c[i] = 0;
    for(i = 0; i < n; ++i) c[x[i] = s[i]]++;
    for(i = 1; i < m; ++i) c[i] += c[i - 1];
    for(i = n - 1; i >= 0; --i) sa[--c[x[i]]] = i;
    for(int k = 1; k <= n; k <<= 1)
    {
        int p = 0;
        for(i = n - k; i < n; ++i) y[p++] = i;
        for(i = 0; i < n; ++i) if(sa[i] >= k) y[p++] = sa[i] - k;
        for(i = 0; i < m; ++i) c[i] = 0;
        for(i = 0; i < n; ++i) c[x[y[i]]]++;
        for(i = 1; i < m; ++i) c[i] += c[i - 1];
        for(i = n - 1; i >= 0; --i) sa[--c[x[y[i]]]] = y[i];
        swap(x, y);
        p = 1; x[sa[0]] = 0;
        for(i = 1; i < n; ++i)
            x[sa[i]] = (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k]) ? p - 1: p++;
        if(p >= n) break;
        m = p;
    }
}

void getHeight(int * s, int n)
{
    int i, j, k = 0;
    for(i = 1; i <= n; ++i) rank[sa[i]] = i;
    for(i = 0; i < n; ++i)
    {
        if(k) k--;
        j = sa[rank[i] - 1];
        while(s[i + k] == s[j + k]) k++;
        height[rank[i]] = k;
    }
}

bool scan(int p, bool f)
{
    for(int i = 2; i <= len; )
    {
        int j = i;
        while(j <= len && height[j] >= p)
        {
            flag[h[sa[j - 1]]] = 1;
            flag[h[sa[j]]] = 1;
            j++;
        }
        int tot = 0;
        for(int k = 0; k < n; ++k) if(flag[k]) tot++;
        memset(flag, 0, sizeof(flag));
        if(tot > n / 2)
        {
            if(!f) return true;
            for(int k = sa[j - 1], q = 0; q < p; ++k, ++q) printf("%c", r[k] + 'a' - 1);
            printf("\n");
        }
        i = j + 1;
    }
    return false;
}

int main()
{
    bool ss = false;
    freopen("in.txt", "r", stdin);
    while(~scanf("%d", &n) && n != 0)
    {
        if(ss) printf("\n");
        else ss = true;
        len = 0;
        int la = 1, ra = 0;
        for(int i = 0; i < n; ++i)
        {
            scanf("%s", str[i]);
            for(int j = 0; ; ++j)
            {
                if(str[i][j] == '\0')
                {
                    r[len] = 27 + i;
                    h[len++] = i;
                    ra = (j > ra) ? j : ra;
                    break;
                }
                r[len] = str[i][j] - 'a' + 1;
                h[len++] = i;
            }
        }
        if(n == 1) // 当n为1的时候，直接输出该字符串
        {
            printf("%s\n", str[0]);
            continue;
        }
        r[len] = 0;
        build_sa(r, len + 1, 27 + n);
        getHeight(r, len);
        if(!scan(1, false)) // 无解
        {
            printf("?\n");
            continue;
        }
        while(la < ra) // 二分答案
        {
            int mid = ((la + ra) >> 1) + 1;
            if(scan(mid, false)) la = mid;
            else ra = mid - 1;
        }
        scan(la, true);
    }
    return 0;
}


/*
3
abcdefg
bcdefgh
cdefghi
3
xxx
yyy
zzz
0

bcdefg
cdefgh

?
*/