XSY 1920 - Mr. Panda and Fantastic Beats

题目精选 后缀数组 二分答案

题意

   Mr. Panda喜欢怪兽。为了找到怪兽，他必须念咒语。
  一天，Mr. Panda在竹林中找到一张纸，上面写着 $N$ 个字符串。
  Mr. Panda的爸爸告诉他，这张纸上隐藏着咒语。
  在这 $N$ 个字符串 $S_1,S_2,...,S_N$ 中，咒语是满足以下两个条件的最短的字符串： ① 该字符串为 $S_1$ 的子串 ② 该字符串不是 $S_2,S_3,...,S_N$ 的子串。
  如果有解，输出字典序最小的一组。如果无解，输出 Impossible 。

   $n\le 50000$
   $\sum |S|\le 250000$

分析

  考虑将所有字符串接起来，将相邻两个字符串中间用一个不同的字符接起来，求一次 $SA$ 和 $height$ 。
  二分答案。假设当前的答案为 $len$ ，根据 $height$ 数组将 $SA$ 进行分段。对于每个字符串 $|S|$ ，若 $|S|$ 能作为答案，当且仅当它在块内满足要求。这是因为它和块外的 $LCP$ 小于 $len$ ，所以外界对其无影响。
  块内满足要求，当且仅当每个坐标都属于第一个字符串，且字符串的长度至少为 $len$ 。我们记录 $mx$ 为最大的坐标，以及 $mn$ 为最小的坐标，即可判定并求解。

实现

#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
#define F(i,a,b) for (int i=(a);i<=(b);i++)
#define D(i,a,b) for (int i=(a);i>=(b);i--)
const int N=300005;
const int LIM=200;
int nT;
int n;
int s[N]; int ns;
int fini;
int sa[N],rk[N],ht[N];
int sum[N],trk[N],tsa[N];
inline int rd(void) {
    int x=0,f=1; char c=getchar();
    for (;!isdigit(c);c=getchar()) if (c=='-') f=-1;
    for (;isdigit(c);c=getchar()) x=x*10+c-'0';
    return x*f;
}
void Prework(void) {
    memset(sa,0,sizeof sa);
    memset(rk,0,sizeof rk);
    memset(ht,0,sizeof ht);
    memset(sum,0,sizeof sum);
    memset(trk,0,sizeof trk);
    memset(tsa,0,sizeof tsa);
    int lim=LIM+ns;
    F(i,1,ns) sum[rk[i]=s[i]]++;
    F(i,1,lim) sum[i]+=sum[i-1];
    D(i,ns,1) sa[sum[rk[i]]--]=i;
    rk[sa[1]]=lim=1;
    F(i,2,ns) {
        if (s[sa[i]]!=s[sa[i-1]]) lim++;
        rk[sa[i]]=lim;
    }
    for (int j=1;lim!=ns;j<<=1) {
        int p=0; memset(tsa,0,sizeof tsa);
        F(i,ns-j+1,ns) tsa[++p]=i;
        F(i,1,ns) if (sa[i]>j) tsa[++p]=sa[i]-j;
        memset(sum,0,sizeof sum);
        memcpy(trk,rk,sizeof rk);
        F(i,1,ns) sum[rk[i]=trk[tsa[i]]]++;
        F(i,1,lim) sum[i]+=sum[i-1];
        D(i,ns,1) sa[sum[rk[i]]--]=tsa[i];
        rk[sa[1]]=lim=1;
        F(i,2,ns) {
            if (trk[sa[i]]!=trk[sa[i-1]]||trk[sa[i]+j]!=trk[sa[i-1]+j]) lim++;
            rk[sa[i]]=lim;
        }
    }
    int p=0;
    F(i,1,ns) {
        if (p>0) p--;
        while (s[i+p]==s[sa[rk[i]-1]+p]) p++;
        ht[rk[i]]=p;
    }
}
int Check(int len) {
    F(l,1,ns) {
        int r=l; while (r+1<=ns&&ht[r+1]>=len) r++;
        int mx=0; F(i,l,r) mx=max(mx,sa[i]);
        if (mx>fini) {
            l=r; continue;
        }
        int mn=ns+1; F(i,l,r) mn=min(mn,sa[i]);
        if (fini-mn+1>=len) return 1;
        l=r;
    }
    return 0;
}
void Make(char *t,int len) {
    F(l,1,ns) {
        int r=l; while (r+1<=ns&&ht[r+1]>=len) r++;
        int mx=0; F(i,l,r) mx=max(mx,sa[i]);
        if (mx>fini) {
            l=r; continue;
        }
        int mn=ns+1; F(i,l,r) mn=min(mn,sa[i]);
        if (fini-mn+1>=len) {
            F(i,l,r) if (fini-sa[i]+1>=len) {
                int tot=0;
                F(j,sa[i],sa[i]+len-1)
                    t[++tot]=s[j];
                t[++tot]=0;
                break;
            }
            return;
        }
        l=r;
    }
}
int main(void) {
    #ifndef ONLINE_JUDGE
        freopen("sdchr.in","r",stdin);
        freopen("sdchr.out","w",stdout);
    #endif
    cin>>nT;
    F(c,1,nT) {
        memset(s,0,sizeof s); ns=fini=0;
        n=rd();
        F(i,1,n) {
            static char t[N]; scanf("%s",t+1);
            int nt=strlen(t+1);
            if (i==1) fini=nt;
            F(j,1,nt) s[++ns]=t[j];
            s[++ns]=i+LIM;
        }
        Prework();
        int l=1,r=fini;
        if (!Check(r)) {
            printf("Case #%d: Impossible\n",c); continue;
        }
        while (l<r) {
            int mid=(int)floor((l+r)/2.0);
            if (Check(mid))
                r=mid;
            else l=mid+1;
        }
        static char t[N]; Make(t,l);
        printf("Case #%d: %s\n",c,t+1);
    }
    return 0;
}