Suffix Array 后缀数组DA算法模板(带ST表)
字符串   发布于 2019-08-26   510人围观  0条评论
字符串   发表于 2019-08-26   510人围观  0条评论
//后缀数组sa[i]就表示排名为i的后缀的起始位置的下标
//而它的映射数组rk[i]就表示起始位置的下标为i的后缀的排名
//height[i]表示lcp(i,i-1),s为下标1 to len
char s[maxn];
int y[maxn], x[maxn], c[maxn], sa[maxn], rk[maxn], height[maxn];
int n, m;
inv get_SA() {
    memset(c, 0, sizeof(c));
    for (int i = 1; i <= n; ++i) ++c[x[i] = s[i]];
    for (int i = 2; i <= m; ++i) c[i] += c[i - 1];
    for (int i = n; i >= 1; --i) sa[c[x[i]]--] = i;
    for (int k = 1; k <= n; k <<= 1) {
        int num = 0;
        for (int i = n - k + 1; i <= n; ++i) y[++num] = i;
        for (int i = 1; i <= n; ++i) if (sa[i] > k) y[++num] = sa[i] - k;
        for (int i = 1; i <= m; ++i) c[i] = 0;
        for (int i = 1; i <= n; ++i) ++c[x[i]];
        for (int i = 2; i <= m; ++i) c[i] += c[i - 1]; 
        for (int i = n; i >= 1; --i) sa[c[x[y[i]]]--] = y[i], y[i] = 0;
        swap(x, y);
        x[sa[1]] = 1;
        num = 1;
        for (int i = 2; i <= n; ++i)
            x[sa[i]] = (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k]) ? num : ++num;
        if (num == n) break;
        m = num;
    }
}
void get_height() {
    int k = 0;
    for (int i = 1; i <= n; ++i) rk[sa[i]] = i;
    for (int i = 1; i <= n; ++i) {
        if (rk[i] == 1) continue;
        if (k) --k;
        int j = sa[rk[i] - 1];
        while (j + k <= n && i + k <= n && s[i + k] == s[j + k]) ++k;
        height[rk[i]] = k;
    }
    return;
}
void build_st() {
    for (int i = 1; i <= n; i++) st[0][i] = height[i];
    for (int k = 1; k <= 19; k++) {
        for (int i = 1; i + (1 << k) - 1 <= n; i++) {
            st[k][i] = min(st[k - 1][i], st[k - 1][i + (1 << k - 1)]);
        }
    }
    return;
}
int lcp(int x, int y) {
    int l = rk[x], r = rk[y];
    if (l > r) swap(l, r);
    if (l == r) return n - sa[l];
    int t = log2(r - l);
    return min(st[t][l + 1], st[t][r - (1 << t) + 1]);
}


上一篇: 2018-2019 ACM-ICPC, Asia Shenyang Regional Contest E.The Kouga Ninja Scrolls 曼哈顿距离转换契比雪夫距离 + 线段树单点修改

下一篇: 2019 CCPC网络赛 1005 huntian oy 杜教筛

立即登录,发表评论
没有帐号?立即注册
0 条评论