luogu4770 [NOI2018]你的名字

题目背景

实力强大的小A 被选为了ION2018 的出题人,现在他需要解决题目的命名问题。

题目描述

小A 被选为了ION2018 的出题人,他精心准备了一道质量十分高的题目,且已经把除了题目命名以外的工作都做好了。

由于ION 已经举办了很多届,所以在题目命名上也是有规定的,ION 命题手册规定:每年由命题委员会规定一个小写字母字符串,我们称之为那一年的命名串,要求每道题的名字必须是那一年的命名串的一个非空连续子串,且不能和前一年的任何一道题目的名字相同。

由于一些特殊的原因,小A 不知道ION2017 每道题的名字,但是他通过一些特殊手段得到了ION2017 的命名串,现在小A 有Q 次询问:每次给定ION2017 的命名串和ION2018 的命名串,求有几种题目的命名,使得这个名字一定满足命题委员会的规定,即是ION2018 的命名串的一个非空连续子串且一定不会和ION2017 的任何一道题目的名字相同。

由于一些特殊原因,所有询问给出的ION2017 的命名串都是某个串的连续子串,详细可见输入格式。

输入格式

第一行一个字符串S ,之后询问给出的ION2017 的命名串都是S 的连续子串。 第二行一个正整数Q,表示询问次数。 接下来Q 行,每行有一个字符串T 和两个正整数$l,r$,表示询问如果ION2017 的 命名串是$S[l..r]$,ION2018 的命名串是T 的话,有几种命名方式一定满足规定。

输出格式

输出Q 行,第i 行一个非负整数表示第i 个询问的答案。

样例输入

scbamgepe
3
smape 2 7
sbape 3 8
sgepe 1 9

样例输出

12
10
4

说明

$|S|\le 5\times 10^5$,$Q\le 10^5$,$\sum|T|\le 10^6$


分析

题目大意:求询问串$p$中有多少不同的串没有在主串$s$的$[l,r]$区间中出现过。

先简化一下问题:把【不同的串】和【$[l,r]$区间】这两个限制去掉。那这个问题就很简单了,把$p$在$s$上跑匹配,求出$p$的前缀$p[1\dots i]$在$s$上能匹配到的最大长度$lim(i)$,则$ans=\sum{i-lim(i)}$。

现在加上【不同的串】这个限制,就需要去一下重。刚开始想的一个sb操作是在$s$的SAM上用树剖什么的乱搞,非常不可写。实际上去重不一定要在$s$上做,也可以在$p$上去重。

考虑SAM可以把所有相同串合并到同一个状态里,所以先建出$p$的SAM,然后对于每个状态$u$,我们计算$[min(u),max(u)]$中有几个长度对应的串在$s$中没有出现。

之前我们已经算出了$lim(i)$。对于状态$u$,我们在它的right集合中随便抓一个数$pos$。若$lim(pos)\ge max(u)$,那么这个状态都在$s$中出现,对答案没有贡献。否则$u$对答案的贡献为$max(u)-\max\{min(u)-1,lim(u)\}$。

现在再加上【$[l,r]$区间】这个限制,难道要把$s[l\dots r]$的SAM建出来?其实并不需要。设当前匹配长度为$len$,那么如果一个状态的right集合中没有$[l+len-1,r]$中的数,就说明这个状态没有长度为$len$且在$s[l\dots r]$范围内的串,那我们就当这个状态不存在。

维护每个节点的right集合,可以使用线段树合并。总复杂度$O(n\log n)$。

代码

#include <bits/stdc++.h>

const int N = 1e6;

char s[N];
int n;
char p[N];
int m, l, r;
int lim[N];

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

    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 u, int pos) {
        init(root[u], 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 u, int l, int r) {
        if (l > r) return false;
        return find(root[u], 1, n, l, r);
    }
}

struct Sam {
    static const int SZ = N << 1;
    int top, last;
    int ch[SZ][26], fa[SZ], mx[SZ], rpos[SZ];
    int buc[N], id[SZ];

    Sam() {
        clear();
    }

    int newNode() {
        top++;
        memset(ch[top], 0, sizeof ch[top]);
        fa[top] = mx[top] = rpos[top] = 0;
        return top;
    }

    void clear() {
        top = 0;
        last = newNode();
    }

    void extend(char c, int pos, bool buildTree) {
        int x = c - 'a', p = last;
        int np = last = newNode();
        mx[np] = mx[p] + 1;
        rpos[np] = pos;
        if (buildTree) 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 = newNode();
        mx[nq] = mx[p] + 1;
        rpos[nq] = pos;
        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 sort() {
        memset(buc, 0, sizeof buc);
        for (int i = 1; i <= top; i++)
            buc[mx[i]]++;
        for (int i = 1; i <= top; i++)
            buc[i] += buc[i-1];
        for (int i = 1; i <= top; i++)
            id[buc[mx[i]]--] = i;
    }

    void work() {
        sort();
        for (int i = top; i >= 2; i--) {
            int u = id[i];
            Seg::merge(fa[u], u);
        }
    }
} sam1, sam2;

void solve() {
    scanf("%s%d%d", p+1, &l, &r);
    m = strlen(p+1);
    sam2.clear();
    for (int i = 1; i <= m; i++)
        sam2.extend(p[i], i, false);

    for (int u = 1, len = 0, i = 1; i <= m; i++) {
        int x = p[i] - 'a';
        while (true) {
            if (sam1.ch[u][x] && Seg::find(sam1.ch[u][x], l+len, r)) {
                u = sam1.ch[u][x];
                len++;
                break;
            }
            if (len == 0) break;
            if (--len == sam1.mx[sam1.fa[u]])
                u = sam1.fa[u];
        }
        lim[i] = len;
    }


    long long ans = 0;
    for (int i = 2; i <= sam2.top; i++) {
        ans += std::max(0, sam2.mx[i] - std::max(sam2.mx[sam2.fa[i]], lim[sam2.rpos[i]]));
    }
    printf("%lld\n", ans);
}

int main() {
    scanf("%s", s+1);
    n = strlen(s+1);
    for (int i = 1; i <= n; i++)
        sam1.extend(s[i], i, true);
    sam1.work();

    int q; scanf("%d", &q);
    while (q--) solve();
    return 0;
}


转载请注明出处。


评论列表,共 0 条评论

    暂无评论

发表评论