bzoj4556 [Tjoi2016&Heoi2016]字符串

题目描述

佳媛姐姐过生日的时候,她的小伙伴从某东上买了一个生日礼物。生日礼物放在一个神奇的箱子中。箱子外边写了一个长为n的字符串s,和m个问题。佳媛姐姐必须正确回答这m个问题,才能打开箱子拿到礼物,升职加薪,出任CEO,嫁给高富帅,走上人生巅峰。每个问题均有a,b,c,d四个参数,问你子串s[a..b]的所有子串和s[c..d]的最长公共前缀的长度的最大值是多少?佳媛姐姐并不擅长做这样的问题,所以她向你求助,你该如何帮助她呢?

输入格式

输入的第一行有两个正整数n,m,分别表示字符串的长度和询问的个数。接下来一行是一个长为n的字符串。接下来m行,每行有4个数a,b,c,d,表示询问s[a..b]的所有子串和s[c..d]的最长公共前缀的最大值。1<=n,m<=100,000,字符串中仅有小写英文字母,a<=b,c<=d,1<=a,b,c,d<=n

输出格式

对于每一次询问,输出答案。

样例输入

5 5
aaaaa
1 1 1 5
1 5 1 1
2 3 2 3
2 4 2 3
2 3 2 4

样例输出

1
1
2
2
2

分析

题目大意:求$s[a\dots b]$的子串与$s[c\dots d]$的LCP的最大长度。

首先,子串问题一般用SA或SAM处理,所以要先把LCP转成LCS(最长公共后缀)比较好做,也就是先把串翻转。

直接求不好求,发现答案可以二分,转化成判断$s[d-mid+1\dots d]$是否在$s[a\dots b]$中出现。

如果我们建出了$s$的SAM,那么问题又可以转化成判断$s[d-mid+1\dots d]$所在状态的right集合是否包含$[a,b]$中的数。

要找$s[d-mid+1\dots d]$所在状态,可以在parent树上倍增,从后缀$s[1\dots d]$所在状态往上倍增找$mx\ge mid$的深度最浅的节点。

至于查询状态$u$的right集合是否包含$[a,b]$中的数,最裸的方法是按dfs序建主席树,对$u$进行子树查询就可以得到$u$的right集合。不过也可以用线段树合并实现,合并完后$u$的线段树存的就是$u$的子树合并起来的信息了。时空复杂度也都是$O(n\log n)$。

代码

#include <bits/stdc++.h>

const int N = 1e5+50;
const int D = 20;

int n, m;
char s[N];

namespace Seg {
    const int SIZ = 2*N*D;
    int top, root[SIZ];
    int ls[SIZ], rs[SIZ];

    void init(int &u, int L, int R, int pos) {
        u = ++top;
        if (L == R) return;
        int mid = L + R >> 1;
        if (pos <= mid) init(ls[u], L, mid, pos);
        else init(rs[u], mid+1, R, pos);
    }

    void init(int id, int pos) {
        init(root[id], 1, n, pos);
    }

    int mergeNode(int u, int v) {
        if (!u || !v) return u+v;
        int x = ++top;
        ls[x] = mergeNode(ls[u], ls[v]);
        rs[x] = mergeNode(rs[u], rs[v]);
        return x;
    }

    void merge(int u, int v) {
        root[u] = mergeNode(root[u], root[v]);
    }

    bool find(int u, int L, int R, int l, int r) {
        if (!u) return false;
        if (L == l && R == r) return true;
        int mid = L + R >> 1;
        bool rtn = false;
        if (l <= mid) rtn |= find(ls[u], L, mid, l, std::min(mid, r));
        if (r > mid) rtn |= find(rs[u], mid+1, R, std::max(mid+1, l), r);
        return rtn;
    }

    bool find(int id, int l, int r) {
        return find(root[id], 1, n, l, r);
    }
}

namespace Sam {
    const int SIZ = N << 1;
    int top = 1, last = 1;
    int ch[SIZ][26], fa[SIZ], mx[SIZ];
    int uid[N];  // 前缀i对应的np编号 
    int anc[SIZ][D];
    int buc[N], id[SIZ];

    void extend(char c, int pos) {
        int x = c - 'a', p = last;
        int np = last = ++top;
        uid[pos] = np;
        mx[np] = mx[p] + 1;
        Seg::init(np, pos);
        for (; p && !ch[p][x]; p = fa[p])
            ch[p][x] = np;
        if (!p) {
            fa[np] = 1;
            return;
        }
        int q = ch[p][x];
        if (mx[q] == mx[p] + 1) {
            fa[np] = q;
            return;
        }
        int nq = ++top;
        mx[nq] = mx[p] + 1;
        fa[nq] = fa[q];
        fa[q] = fa[np] = nq;
        memcpy(ch[nq], ch[q], sizeof ch[nq]);
        for (; ch[p][x] == q; p = fa[p])
            ch[p][x] = nq;
    }

    void build(char s[]) {
        for (int i = 1; i <= n; i++)
            extend(s[i], i);

        for (int i = 1; i <= top; i++)
            buc[mx[i]]++;
        for (int i = 1; i <= mx[last]; i++)
            buc[i] += buc[i-1];
        for (int i = 1; i <= top; i++)
            id[buc[mx[i]]--] = i;

        for (int i = top; i >= 1; i--) {
            int u = id[i];
            if (u == 1) continue;
            Seg::merge(fa[u], u);
        }

        for (int i = 1; i <= top; i++) {
            int u = id[i];
            anc[u][0] = fa[u];
            for (int j = 1; j < D; j++)
                anc[u][j] = anc[anc[u][j-1]][j-1];
        }
    } 
}

bool check(int right, int len, int l, int r) {
    int u = Sam::uid[right];
    for (int i = D-1; i >= 0; i--) {
        int v = Sam::anc[u][i];
        if (Sam::mx[v] >= len)
            u = v;
    }
    return Seg::find(u, l, r);
}

int main() {
    scanf("%d%d%s", &n, &m, s+1);
    std::reverse(s+1, s+n+1);
    Sam::build(s);
    for (int a, b, c, d; m--; ) {
        scanf("%d%d%d%d", &a, &b, &c, &d);
        a = n-a+1; b = n-b+1; c = n-c+1; d = n-d+1;
        std::swap(a, b); std::swap(c, d);
        int l = 1, r = std::min(b-a+1, d-c+1), ans = 0;
        while (l <= r) {
            int mid = l + r >> 1;
            if (check(d, mid, a+mid-1, b)) {
                ans = mid;
                l = mid + 1;
            } else r = mid - 1;
        }
        printf("%d\n", ans);
    }
    return 0;
}


转载请注明出处。


评论列表,共 0 条评论

    暂无评论

发表评论