uva 11107 （后缀数组入门）

Myth丶恋晨 2022-05-19 11:07 139阅读 0赞

思路：找出现次数大于n/2次的最大子串，一个子串出现多次，那么他们的排名肯定是相邻的，所以利用height数组，找出相邻排名最长公共前缀长度等于 K 的区间。看看这个区间中的个数是否大于n/2， 满足的话这个k长度就符合。所有我们需要枚举k的大小，可以用二分查找这个临界点。

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int INF=1<<30;
    const int N=1e5+1000;
    int t1[N], t2[N], c[N], MAX;
    
    bool cmp(int *r, int a, int b, int l){
        return r[a]==r[b] && r[a+l]==r[b+l];
    }
    
    void da(int str[], int sa[], int rk[], int height[], int n, int m){
        n++;
        int i, j, p, *x=t1, *y=t2;
    
        for(i=0; i<m; i++) c[i]=0;
        for(i=0; i<n; i++) c[x[i]=str[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(j=1; j<=n; j<<=1){
            p=0;
            for(i=n-j; i<n; i++) y[p++]=i;
            for(i=0; i<n; i++) if(sa[i]>=j) y[p++]=sa[i]-j;
    
            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]]=cmp(y, sa[i-1], sa[i], j) ? p-1 : p++;
            if(p>=n) break;
            m=p;
        }
        int k=0;
        n--;
        for(i=0; i<=n; i++) rk[sa[i]]=i;
        for(i=0; i<n; i++){
            if(k)k--;
            j=sa[rk[i]-1];
            while(str[i+k]==str[j+k]) k++;
            height[rk[i]]=k;
        }
    }
    
    int rk[N], height[N], sa[N], n, s[N], cnt, id[N];
    char str[10000];
    
    bool judge(int len, bool f){
        set<int> st;
        st.insert(id[sa[0]]);
        for(int i=0; i<=cnt; i++){
    
            while(i<cnt && height[i]>=len){
                st.insert(id[sa[i]]);
                i++;
            }
    
            if(st.size()>n/2){
                if(f)
                    return true;
    
                for(int j=sa[i-1]; j<sa[i-1]+len; j++)
                    putchar(s[j]+'a'-1);
                puts("");
            }
    
            st.clear();
            st.insert(id[sa[i]]);
        }
        return false;
    }
    
    void solve(){
    
        if(!judge(1, 1)){
            puts("?");
            return;
        }
        int l=1, r=MAX;
        while(l<=r){
            int mid=(l+r)>>1;
            if(judge(mid, 1)){
                l=mid+1;
            }
            else
                r=mid-1;
        }
    
        judge(r, 0);
    }
    
    void init(){
        MAX=0; cnt=0;
    }
    
    int main(){
        int f=0;
        while(~scanf("%d", &n) && n){
            init();
            if(f) puts("");
            if(!f) f=1;
    
            for(int i=1; i<=n; i++){
                scanf("%s", str);
                MAX=max(MAX, (int)strlen(str));
                for(int j=0; str[j]; j++){
                    id[cnt]=i;
                    s[cnt++]=str[j]-'a'+1;
                }
                id[cnt]=i;
                s[cnt++]=26+i;
            }
            s[cnt]=0;
    
            if(n==1){
                puts(str);
                continue;
            }
    
            da(s, sa, rk, height, cnt, 26+n+1);
    
            solve();
        }
    
        return 0;
    }