[BZOJ2882/Luogu1368]工艺(后缀数组)

发布于 2018-03-25  83 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ2882/Luogu1368]工艺(后缀数组)

Description

小敏和小燕是一对好朋友。
他们正在玩一种神奇的游戏,叫Minecraft。
他们现在要做一个由方块构成的长条工艺品。但是方块现在是乱的,而且由于机器的要求,他们只能做到把这个工艺品最左边的方块放到最右边。
他们想,在仅这一个操作下,最漂亮的工艺品能多漂亮。
两个工艺品美观的比较方法是,从头开始比较,如果第i个位置上方块不一样那么谁的瑕疵度小,那么谁就更漂亮,如果一样那么继续比较第i+1个方块。如果全都一样,那么这两个工艺品就一样漂亮。

Tag

后缀数组

解决思路

把字符串复制一遍接在后面,问题转化为求长度大于等于原字符串长度的最小的后缀。后缀排序解决。

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

#define ll long long
#define mem(Arr,x) memset(Arr,x,sizeof(Arr))

const int maxN=300100*2;
const int inf=2147483647;

int n;
int Arr[maxN];
int SA[maxN],Rank[maxN];
int CntA[maxN],CntB[maxN],A[maxN],B[maxN],SSA[maxN];

int main()
{
    ios::sync_with_stdio(false);
    cin>>n;
    for (int i=1;i<=n;i++){
        cin>>Arr[i];Arr[i+n]=Arr[i];
    }
    n=n+n;
    for (int i=1;i<=n;i++) CntA[Arr[i]]++;
    for (int i=1;i<maxN;i++) CntA[i]+=CntA[i-1];
    for (int i=n;i>=1;i--) SA[CntA[Arr[i]]--]=i;
    Rank[SA[1]]=1;
    for (int i=2;i<=n;i++)
    {
        Rank[SA[i]]=Rank[SA[i-1]];
        if (Arr[SA[i]]!=Arr[SA[i-1]]) Rank[SA[i]]++;
    }
    for (int l=1;Rank[SA[n]]<n;l=l<<1)
    {
        mem(CntA,0);mem(CntB,0);
        for (int i=1;i<=n;i++)
        {
            CntA[A[i]=Rank[i]]++;
            CntB[B[i]=((i+l<=n)?(Rank[i+l]):(0))]++;
        }
        for (int i=1;i<maxN;i++) CntA[i]+=CntA[i-1],CntB[i]+=CntB[i-1];
        for (int i=n;i>=1;i--) SSA[CntB[B[i]]--]=i;
        for (int i=n;i>=1;i--) SA[CntA[A[SSA[i]]]--]=SSA[i];
        Rank[SA[1]]=1;
        for (int i=2;i<=n;i++)
        {
            Rank[SA[i]]=Rank[SA[i-1]];
            if ((A[SA[i]]!=A[SA[i-1]])||(B[SA[i]]!=B[SA[i-1]])) Rank[SA[i]]++;
        }
    }
    int pos;
    for (int i=1;i<=n;i++)
        if (SA[i]<=n/2){
            pos=SA[i];break;
        }
    for (int i=1;i<=n/2;i++) cout<<Arr[pos+i-1]<<" ";cout<<endl;
    return 0;
}

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ2882/Luogu1368]工艺(后缀数组)


HNCJ OIer