首页 > > 程序设计 > C/C++ >

LOJ#111. 后缀排序(二分 hash)

2018-08-02 05:43:58来源：博客园阅读 ()

题意

给出一个字符串，求出排名为$i$个字符串在原串中的开始位置

Sol

纪念一下这伟大的时刻qwq。

我用二分+hash把这题水过去了qwq。

#include<cstdio>
#include<cstring>
#include<algorithm>
#define ull long long 
const int MAXN = 1e6 + 10;
ull h[MAXN], base[MAXN], seed = 997;
int N, a[MAXN], sa[MAXN], tot;
char s[MAXN];
ull gethash(int l, int r) {return h[l] - h[r + 1] * base[r - l + 1];}
bool check(int a, int b, int mid) {
    if((a + mid - 1 > N) || (b + mid - 1 > N) || (a < 1) || (b < 1)) return 0;
    return gethash(a, a + mid - 1) == gethash(b, b + mid - 1);
}
bool comp(int a, int b) {
    int l = 0, r = N, ans = 0;
    while(l <= r) {
        int mid = l + r >> 1;
        if(check(a, b, mid)) l = mid + 1, ans = mid;
        else r = mid - 1;
    }
    return s[a + ans] < s[b + ans];
}
int main() {
    scanf("%s", s + 1);
    N = strlen(s + 1);
    for(int i = 1; i <= N; i++) a[i] = i;
    base[0] = 1;
    for(int i = 1; i <= N; i++) base[i] = base[i - 1] * seed;
    for(int i = N; i >= 1; i--) h[i] = h[i + 1] * seed + s[i];
    std::sort(a + 1, a + N + 1, comp);
    for(int i = 1; i <= N; i++) printf("%d ", a[i]);
    return 0;
}