CODE

贴上大常数选手的代码

#include<bits/stdc++.h>

using namespace std;

char cb[1<<15],*cs=cb,*ct=cb;

#define getc() (cs==ct&&(ct=(cs=cb)+fread(cb,1,1<<15,stdin),cs==ct)?0:*cs++)

template<class T>inline void read(T &res) {

	char ch; int flg = 1; while(!isdigit(ch=getchar()))if(ch=='-')flg=-flg;

	for(res=ch-'0';isdigit(ch=getchar());res=res*10+ch-'0'); res*=flg;

}

const int MAXN = 600005;

int s[MAXN];

int x[MAXN], y[MAXN], c[MAXN], rk[MAXN], sa[MAXN];

inline void Get_Sa(int n, int m) {

    for(int i = 1; i <= m; ++i) c[i] = 0;

    for(int i = 1; i <= n; ++i) ++c[x[i]=s[i]];

    for(int i = 2; i <= m; ++i) c[i] += c[i-1];

    for(int i = n; i >= 1; --i) sa[c[x[i]]--] = i;

    for(int k = 1; k <= n; k<<=1) {

        int p = 0;

        for(int i = n-k+1; i <= n; ++i) y[++p] = i;

        for(int i = 1; i <= n; ++i) if(sa[i]>k) y[++p] = sa[i]-k;

        for(int i = 1; i <= m; ++i) c[i] = 0;

        for(int i = 1; i <= n; ++i) ++c[x[i]];

        for(int i = 2; i <= m; ++i) c[i] += c[i-1];

        for(int i = n; i >= 1; --i) sa[c[x[y[i]]]--] = y[i];

        swap(x, y);

        x[sa[1]] = p = 1;

        for(int i = 2; i <= n; ++i)

            x[sa[i]] = (y[sa[i]] == y[sa[i-1]] && y[sa[i]+k] == y[sa[i-1]+k]) ? p : ++p;

        if((m=p) == n) break;

    }

    for(int i = 1; i <= n; ++i) rk[sa[i]] = i;

}

int n, b[MAXN], tot;

int main() {

	read(n);

	for(int i = 1; i <= n; ++i)

        read(s[i]), b[++tot] = s[i];

    sort(b + 1, b + tot + 1); tot = unique(b + 1, b + tot + 1) - b - 1;

    for(int i = 1; i <= n; ++i)

        s[i] = s[n+i] = lower_bound(b + 1, b + tot + 1, s[i]) - b;

	Get_Sa(n<<1, tot);

	int S;

	for(int i = 1; i <= n+1; ++i)

        if(sa[i] <= n) { S = sa[i]; break; }

	for(int i = 0; i < n; ++i)

        printf("%d ", b[s[S+i]]);

}

巴特西

BZOJ 2882: 工艺 (SA/SAM/最小表示法)

CODE

最新文章

热门文章