Gym - 101194F Mr. Panda and Fantastic Beasts （后缀数组）

题意：给出n个字符串，找到最短的字符串，要求仅为第一个字符串的子串。

思路：把n个字符串用不出现的字符连接起来。其实就是枚举第一个字符串的每一个子串是否是其他字符串的后缀的前缀即可。

#include<cstdio>
#include<cstring>
#include <string>
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN=400000+10;
const int INF=1e9+7;
int n,k;
int rank[MAXN+1];
int tmp[MAXN+1];

//比较（rank[i],rank[i+k]）和(rank[j],rank[j+k])
bool compare_sa(int i,int j){
    if(rank[i]!=rank[j])
        return rank[i]<rank[j];
    else{
        int ri=i+k<=n?rank[i+k]:-1;
        int rj=j+k<=n?rank[j+k]:-1;
        return ri<rj;
    }
}
//rank用来记录字符串的排序，sa用来记录开头字符的位置,S用来记录字符串
//第一个通常是空字符串
//计算字符串S的后缀数组
void construct_sa(string S,int *sa){
    n=S.length();

    //初始长度为1，rank直接取字符的编码.
    for(int i=0;i<=n;i++){
        sa[i]=i;
        rank[i]=i<n?S[i]:-1;
    }

    //利用对长度为k的排序的结果对长度为2k的排序
    for(k=1;k<=n;k*=2){
        sort(sa,sa+n+1,compare_sa);

        //先在tmp中临时储存新计算的rank，再转存回rank中
        tmp[sa[0]]=0;
        for(int i=1;i<=n;i++){
            tmp[sa[i]]=tmp[sa[i-1]]+(compare_sa(sa[i-1],sa[i])?1:0);
        }
        for(int i=0;i<=n;i++){
            rank[i]=tmp[i];
        }
    }
}


//高度数组lcp的计算
void construct_lcp(string S,int *sa,int *lcp){
    int n=S.length();
    for(int i=0;i<=n;i++) rank[sa[i]]=i;

    int h=0;
    lcp[sa[0]]=0;
    for(int i=0;i<n;i++){
        //计算字符串中从位置i开始的后缀及其在后缀数组中的前一个后缀的lcp
        int j=sa[rank[i]-1];

        //将h先减去首字母的1长度，在保持前缀相同的前提下不断地增加
        if(h>0) h--;
        for(;j+h<n&&i+h<n;h++){
            if(S[j+h]!=S[i+h]) break;
        }
        lcp[rank[i]-1]=h;
    }
}

int sa[MAXN],lcp[MAXN];
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
int M[MAXN<<2];
void pushup(int rt){
    M[rt]=min(M[rt<<1],M[rt<<1|1]);
}
void build(int l,int r,int rt){
    if(l==r){
        M[rt]=lcp[l];
        return;
    }
    int m=(l+r)>>1;
    build(lson);
    build(rson);
    pushup(rt);
}
int query(int L,int R,int l,int r,int rt){
    if(L<=l&&R>=r){
        return M[rt];
    }
    int m=(l+r)>>1;
    int res=INF;
    if(L<=m)
        res=min(res,query(L,R,lson));
    if(R>m)
        res=min(res,query(L,R,rson));
    return res;
}
string s;
int len;
int ans,fir;
int cas=1;
int pre[MAXN],nxt[MAXN];
void solve(){
    ans=-1,fir=-1;
    memset(pre,0,sizeof pre);
    memset(nxt,0,sizeof nxt);
    int temp=0;
    build(1,n,1);
    for(int i=1;i<=n;i++){
        if(sa[i]>=len){
            temp=i;
        }else{
            pre[i]=temp;
        }
    }
    temp=0;
    for(int i=n;i>=1;i--){
        if(sa[i]>=len){
            temp=i;
        }else{
            nxt[i]=temp;
        }
    }
    for(int i=1;i<=n;i++){
        int MAX=0;
        if(sa[i]<len){
            if(pre[i]){
                MAX=max(MAX,query(pre[i],i-1,1,n,1));
            }
            if(nxt[i]){
                MAX=max(MAX,query(i,nxt[i]-1,1,n,1));
            }
            if((ans==-1||ans>MAX+1)&&sa[i]+MAX+1<=len){
                ans=MAX+1;
                fir=sa[i];
            }
        }
    }
    if(ans==len+1||ans==-1){
        cout<<"Case #"<<cas++<<": Impossible"<<endl;
        return;
    }
    cout<<"Case #"<<cas++<<": ";
    for(int i=fir;i<fir+ans;i++){
        cout<<s[i];
    }
    cout<<endl;
}


int main(){
    std::ios::sync_with_stdio(false);
    int t;
    cin>>t;
    while(t--){
        int num;
        cin>>num;
        memset(lcp,0,sizeof lcp);
        memset(sa,0,sizeof sa);
        memset(rank,0,sizeof rank);
        memset(tmp,0,sizeof tmp);
        s="";
        for(int i=0;i<num;i++){
            string temp;
            cin>>temp;
            if(i)
                s+='$';
            else
                len=temp.length();
            s+=temp;
        }
        n=s.length();
        construct_sa(s,sa);
        construct_lcp(s,sa,lcp);
        solve();
    }
}