M_sea

洛谷5334 [JSOI2019]节日庆典
LuoguLOJ分析显然如果某个位置是答案,那么它至少应该是一个最小的后缀。我们把所有这样的位置称为候选点。可以证...
扫描右侧二维码阅读全文
08
2019/06

洛谷5334 [JSOI2019]节日庆典

Luogu

LOJ

分析

显然如果某个位置是答案,那么它至少应该是一个最小的后缀。我们把所有这样的位置称为候选点

可以证明,候选点最多只有 $\log n$ 个(证明戳这里)。那么我们只要暴力维护所有候选点就行了。

然后从候选点中求答案时要比较某个后缀和原串的字典序大小,可以用 $\text{Z-algorithm}$ 求出所有后缀与源串的 $lcp$ ,那么只要比较下一位即可。当然你用 SA-IS 也是可以的

建议结合代码画图理解。具体实现和细节见代码。

代码

// =================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// =================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <vector>
#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=3000000+10;

int n;
char s[N];
int z[N];
vector<int> ans,tmp;

inline int cmp(int p,int len) {
    if (z[p]>=len) return 0;
    return s[1+z[p]]<s[p+z[p]]?1:-1;
}
inline int check(int x,int y,int len) {
    int res=cmp(y+len-x+1,x-y);
    if (res) return res>0?x:y;
    res=cmp(x-y+1,y-1);
    if (res) return res>0?y:x;
    return y;
}

int main() {
    scanf("%s",s+1); n=strlen(s+1);
    
    for (re int i=2,mid=1,r=1;i<=n;++i) {
        z[i]=r>i?min(z[i-mid+1],r-i):0;
        while (s[1+z[i]]==s[i+z[i]]) ++z[i];
        if (i+z[i]>r) mid=i,r=i+z[i];
    }
    
    for (re int i=1;i<=n;++i) {
        tmp={i};
        for (re int x:ans) {
            while (tmp.size()&&s[x+i-tmp.back()]<s[i]) tmp.pop_back();
            if (!tmp.size()||s[x+i-tmp.back()]==s[i]) {
                while (tmp.size()&&i-x+1<=2*(i-tmp.back()+1)) tmp.pop_back();
                tmp.push_back(x);
            }
        }
        ans=tmp; int pos=ans[0];
        for (re int x:ans)
            if (x!=pos) pos=check(pos,x,i);
        printf("%d ",pos);
    }
    puts(""); return 0;
} 
最后修改:2019 年 06 月 08 日 05 : 16 PM

发表评论