【题解】BZOJ 4556 [TJOI2016&HEOI2016]字符串

Problem

给定长度为 $n$ 的字符串,有 $m$ 个询问

对于每个询问,请输出 $[a,b]$ 内的子串和 $[c,d]$ 的最长公共前缀的长度

Thought

子串,最长公共前缀(要素察觉

考虑将字符串翻转后建立 $SAM$
这样最长公共前缀转化为最长公共后缀

这个东西在 $SAM$ 上就是两点在 $parent$ 树上的 $lca$ 的长度

因为需要求编号在一个区间内的点和另外一个点的最深 $lca$
考虑每次二分长度,然后找到单独点的包含该长度的祖先节点

查询该祖先节点的子树中是否包含区间内的点
这个可以通过主席树来实现

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int read() {
    int ans = 0, flag = 1;
    char ch = getchar();
    while(ch > '9' || ch < '0') {if(ch == '-') flag = - flag; ch = getchar();}
    while(ch >= '0' && ch <= '9') {ans = ans * 10 + ch - '0'; ch = getchar();}
    return ans * flag;
}

const int N = 100010;

int n, m;
char str[N];

int nod[N], pos[N << 1];
int dfn[N << 1], low[N << 1], DFN;

struct Graph {
    int t[N << 1], n[N << 1];
    int head[N << 1], tot;
    void add(int u, int v) {
        ++ tot;
        t[tot] = v;
        n[tot] = head[u];
        head[u] = tot;
    }
}G;

struct SAM {
    int ch[N << 1][26], fa[N << 1], l[N << 1];
    int last = 1, cnt = 1;
    int ins(int c) {
        int x = last, nx = ++ cnt; last = nx; l[nx] = l[x] + 1;
        for(; x && !ch[x][c]; x = fa[x]) ch[x][c] = nx;
        if(!x) fa[nx] = 1;
        else {
            int y = ch[x][c];
            if(l[x] + 1 == l[y]) fa[nx] = y;
            else {
                int ny = ++ cnt; l[ny] = l[x] + 1; fa[ny] = fa[y];
                memcpy(ch[ny], ch[y], sizeof(ch[ny]));
                for(; x && ch[x][c] == y; x = fa[x]) ch[x][c] = ny;
                fa[y] = fa[nx] = ny;
            }
        }
        return nx;
    }
    void build() {
        for(int i = 2; i <= cnt; ++ i)
            G.add(fa[i], i);
    }
}sam;
struct President {
    #define L (ch[x][0])
    #define R (ch[x][1])
    #define mid ((l + r) >> 1)
    int ch[20 * N << 1][2];
    int rt[N << 1], cnt;
    int num[20 * N << 1];
    void ins(int &x, int l, int r, int pos) {
        int now = ++ cnt;
        ch[now][0] = ch[x][0];
        ch[now][1] = ch[x][1];
        num[now] = num[x];

        x = now;
        ++ num[x];

        if(l != r) {
            if(pos <= mid) ins(L, l, mid, pos);
            else ins(R, mid + 1, r, pos);
        }
    }
    int query(int x1, int x2, int l, int r, int ll, int rr) {
        if(!x1 && !x2) return 0;
        if(l >= ll && r <= rr)
            return num[x1] - num[x2];
        else {
            int ans = 0;
            if(mid >= ll)
                ans += query(ch[x1][0], ch[x2][0], l, mid, ll, rr);
            if(mid < rr)
                ans += query(ch[x1][1], ch[x2][1], mid + 1, r, ll, rr);
            return ans;
        }
    }
    void ins(int x, int pos) {
        ins(rt[x], 1, n, pos);
    }
    int query(int x1, int x2, int ll, int rr) {
        if(ll > rr) return 0;
        return query(rt[x1], rt[x2], 1, n, ll, rr);
    }
}tr;

int jp[N << 1][21];

void dfs(int x) {
    dfn[x] = ++ DFN;
    tr.rt[DFN] = tr.rt[DFN - 1];
    if(pos[x]) tr.ins(DFN, pos[x]);
    for(int i = 1; i <= 20; ++ i)
        jp[x][i] = jp[jp[x][i - 1]][i - 1];
    for(int i = G.head[x]; i; i = G.n[i]) {
        int t = G.t[i];
        jp[t][0] = x;
        dfs(t);
    }
    low[x] = DFN;
}

int getGrand(int x, int k) {
    for(int i = 20; i >= 0; -- i)
        if(sam.l[jp[x][i]] >= k && jp[x][i])
            x = jp[x][i];
    return x;
}

bool check(int ll, int rr, int p) {
    return tr.query(low[p], dfn[p] - 1, max(ll, 1), rr);
}

int getL(int ll, int rr, int p, int len) {
    int l = 0, r = len, ans = 0;
    while(l <= r) {
        if(check(ll + mid - 1, rr, getGrand(p, mid))) {
            ans = mid;
            l = mid + 1;
        }
        else
            r = mid - 1;
    }
    return ans;
}

int main() {
    n = read(); m = read();
    scanf("%s", str);
    reverse(str, str + n);
    for(int i = 1; i <= n; ++ i) {
        nod[i] = sam.ins(str[i - 1] - 'a');
        pos[nod[i]] = i;
    }
    sam.build();
    dfs(1);
    for(int i = 1; i <= m; ++ i) {
        int a = n - read() + 1, b = n - read() + 1, c = n - read() + 1, d = n - read() + 1;
        printf("%d\n", getL(b, a, nod[c], c - d + 1));
    }
    return 0;
}
Comments

添加新评论