洛谷1368 工艺

Luogu

分析

最小表示法。

首先将字符串倍长。

考虑维护两个指针 $i,j$ ,表示最小循环表示的起始位置,并暴力求出 $lcp(i,j)$ ,设为 $k$ 。

比较 $s_{i+k}$ 和 $s_{j+k}$ ,如果 $s_{i+k}<s_{j+k}$ ,则 $[j,j+k]$ 内的所有下标都不可能为最小循环的起始位置,那么令 $j\leftarrow j+k+1$ 然后继续比较即可。$s_{j+k}<s_{i+k}$ 的情况同理。

重复以上过程,直到只有一个起始位置即可。

因为 $i,j$ 始终递增,所以时间复杂度 $O(n)$ 。

另外要注意比较的过程中 $i$ 不能等于 $j$ ,所以当出现 $i=j$ 时令其中一个加 $1$ 即可。

代码

// ===================================
//   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=600000+10;

int n,s[N];

inline int solve() {
    int i=1,j=2;
    while (i<=n&&j<=n) { int k=0;
        while (k<=n&&s[i+k]==s[j+k]) ++k;
        s[i+k]<s[j+k]?j+=k+1:i+=k+1;
        if (i==j) ++j;
    }
    return min(i,j);
}

int main() {
    n=read();
    for (re int i=1;i<=n;++i) s[i+n]=s[i]=read();
    int ans=solve();
    for (re int i=0;i<n;++i) printf("%d ",s[ans+i]);
    return 0;
}
最后修改:2019 年 10 月 06 日 04 : 08 PM

发表评论