ref

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
int nn, n, rnk[60005], tmp[60005], cnt[60005], m=128, p, saa[60005];
char s[15], ss[60005];
void sasort(){
    for(int i=0; i<m; i++)  cnt[i] = 0;
    for(int i=0; i<n; i++)  cnt[rnk[i]]++;
    for(int i=1; i<m; i++)  cnt[i] += cnt[i-1];
    for(int i=n-1; i>=0; i--)   saa[--cnt[rnk[tmp[i]]]] = tmp[i];
}
void getSuffixArray(){
    for(int i=0; i<n; i++){
        rnk[i] = ss[i];
        tmp[i] = i;
    }
    sasort();
    for(int j=1; p<n; j<<=1){
        p = 0;
        for(int i=n-j; i<n; i++)    tmp[p++] = i;
        for(int i=0; i<n; i++)
            if(saa[i]>=j)
                tmp[p++] = saa[i] - j;
        sasort();
        p = 1;
        swap(rnk, tmp);
        rnk[saa[0]] = 0;
        for(int i=1; i<n; i++)
            if(tmp[saa[i-1]]==tmp[saa[i]] && tmp[saa[i-1]+j]==tmp[saa[i]+j])
                rnk[saa[i]] = p - 1;
            else
                rnk[saa[i]] = p++;
        m = p;
    }
}
int main(){
    cin>>nn;
    for(int i=0; i<nn; i++){
        scanf("%s", s);
        ss[i] = ss[2*nn-i] = s[0];
    }
    n = nn * 2 + 1;
    getSuffixArray();
    int A=0, B=nn+1;
    while(A+B-nn-1<nn){
        if(rnk[A]<rnk[B])   printf("%c", ss[A++]);
        else    printf("%c", ss[B++]);
        if((A+B-nn-1)%80==0)    printf("\n");
    }
    return 0;
}   

优质内容筛选与推荐>>
1、全屏显示 delphi程序全屏显示无标题栏覆盖整个屏幕(适合屏保)
2、Django 表单
3、<java基础学习>RE 基础语法（2）
4、突然想来说几句
5、索引创建原则

赞赏

长按二维码向我转账

受苹果公司新规定影响，微信 iOS 版的赞赏功能被关闭，可通过二维码转账支持公众号。

阅读

已发送

发送中