洛谷5329 [SNOI2019]字符串

Luogu

LOJ

分析

设 $i<j$ ,考虑怎么比较 $s_i$ 和 $s_j$ 的大小。可以发现我们只需要比较 $a_{i+1\sim j}$ 和 $a_{i\sim j-1}$ 的大小即可。

设 $suf_{i+1}$ 和 $suf_i$ 的 $lcp$ 长度为 $k$ ,那么当 $i+k\geq j$ 时两串显然相等;否则,只需要比较 $a_{i+k}$ 和 $a_{i+k+1}$ 即可。

那么问题就在于如何求出 $lcp(suf_i,suf_{i+1})$ 了,直接 $O(n)$ 从后往前预处理出来即可。

然后就是一个 std::stable_sort 的事情了。

代码

// =================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// =================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=1000000+10;

int n; char s[N];
int h[N],p[N];

inline int cmp(int a,int b) {
    if (a<b) {
        if (a+h[a]>=b) return 1;
        return s[a+h[a]]>s[a+h[a]+1];
    } else {
        if (b+h[b]>=a) return 0;
        return s[b+h[b]]<s[b+h[b]+1];
    }
}

int main() {
    n=read(); scanf("%s",s+1);
    for (re int i=n-1;i;--i) h[i]=s[i]==s[i+1]?h[i+1]+1:0;
    for (re int i=1;i<=n;++i) p[i]=i;
    stable_sort(p+1,p+n+1,cmp);
    for (re int i=1;i<=n;++i) printf("%d ",p[i]); puts("");
    return 0;
}
最后修改:2019 年 10 月 05 日 10 : 25 AM

发表评论