BZOJ 3881 - [Coci2015]Divljak

#字符串 #AC自动机 #树链剖分 #Fail树 #树链的并

Published on 2016-07-01

题目地址

描述

Alice 有 $n$ 个字符串 $s_1, s_2, \cdots, s_n$ ，Bob 有一个字符串集合 $T$ ，一开始集合是空的。
接下来会发生 $q$ 个操作，操作有两种形式：

1 P，Bob 往自己的集合里添加了一个字符串 $P$ 。
2 x，Alice 询问 Bob，集合 $T$ 中有多少个字符串包含串 $S_x$ 。（我们称串 $A$ 包含串 $B$ ，当且仅当 $B$ 是 $A$ 的子串）

Bob 遇到了困难，需要你的帮助。

分析

先看暴力做法：对 $s_1, s_2, \cdots, s_n$ 建立 AC 自动机，然后对于每个 $P$ ，对 $P$ 跑匹配，用后缀链接 $\mathrm{last}$ 跑出（不是跑 $\mathrm{fail}$ ）所有能匹配的 $s$ ，然后累加答案即可，注意一个 $s$ 只能计算一次。询问用 $O(1)$ 直接回答。

上述做法的瓶颈在于跑后缀链接这里，它是有可能跑 $O(n)$ 次的，比如所有的 $s$ 全是 a，然后 $P$ 是 aaaaaaaaaa，那么直接被卡到 $O(n^2)$ ，无法承受。

AC 自动机有两棵树，这两棵树的点是相同的，但是边不同，一个是普通的 $\mathrm{Trie}$ 树，一个是 $\mathrm{fail}$ 树（将 $\mathrm{fail}$ 函数看做连向父亲的边）。
假设我们要匹配 $P$ ，之前我们的暴力是在 $\mathrm{Trie}$ 上跑，再对经过的每一个点跑后缀链接 $\mathrm{last}$ 直到根，但是为了具有普遍性，我们跑 $\mathrm{fail}$ 树，什么意思呢？在某一个点跑后缀链接的过程，其实就是在后缀链接形成的树上走到根，到根路径上经过的每一个点都是一个单词末尾节点。而跑 $\mathrm{fail}$ 的过程，是在 $\mathrm{fail}$ 形成的树上走到根，到根路径上的经过的每一个点（每个点在 $\mathrm{Trie}$ 上唯一代表一个字符串）都是 $P$ 的子串，而且是可以被 AC 自动机成功匹配的子串，但是这个子串不一定是一个完整的单词，但所有这些子串，一包含跑后缀链接跑到的那些串。
换句话说，匹配 $P$ ，将 $P$ 先在 $\mathrm{Trie}$ 上跑，经过一系列点，这些点再各自跑 $\mathrm{fail}$ 树到根，经过的所有点的并，就是 AC 自动机所有能识别的 $P$ 的子串，但这些子串，不一定就是一个完整的单词！

那么对应到这道题，我们就将一个暴力的过程，转换为了在树上的操作，每次将若干个点到根的路径取并集，将并集上的点全部 +1。
首先将点 $u$ 到根的路上的点全部 +1，这个可以转化为 DFS 序，在 $u$ 上 +1，询问 $v$ 的权值时，只需询问子树的权值和，用树状数组即可快速操作。
并集怎么办呢？我们将所有点按照 DFS 序排序，得到 $p_1, p_2, p_3\cdots$ 一开始将 $p_1$ 到根 +1，接着再将 $p_2$ 到根 +1，然后再将 $\mathrm{LCA}(p_1, p_2)$ 到根 -1。也就是每个点到根都 +1，然后相邻两个点的 $\mathrm{LCA}$ 到根 -1。为什么？我们要减去交集，只有 DFS 序靠近的点，到根的路径才可能拥有最大的交集，如果 $p_{i - 2}, p_{i - 1}$ 的交集为 $u$ ，那么 $p_{i - 1}, p_i$ 的交集必定小于等于 $u$ ，所以是正确的。

用树链剖分维护这些东西，即可 $O(m\log n)$ 解决问题。

代码

//  Created by Sengxian on 7/1/16.
//  Copyright (c) 2016年 Sengxian. All rights reserved.
//  BZOJ 3881 AC 自动机 + 树链的并
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
inline int ReadInt() {
    static int n, ch;
    n = 0, ch = getchar();
    while (!isdigit(ch)) ch = getchar();
    while (isdigit(ch)) n = (n << 3) + (n << 1) + ch - '0', ch = getchar();
    return n; 
}

const int maxn = 100000 + 3, maxLen = 2000000 + 3;
int n, strID[maxn];
char str[maxLen];

namespace AhoCorasickAutomata {
    const int maxNode = maxLen, maxChar = 26;
    int ch[maxNode][maxChar], f[maxNode], sz;
    void init() {
        memset(ch[0], 0, sizeof ch[0]);
        sz = 1;
    }
    void insert(char *str, int id) {
        int cur = 0;
        for (int i = 0; str[i]; ++i) {
            int c = str[i] - 'a';
            if (!ch[cur][c]) {
                memset(ch[sz], 0, sizeof ch[sz]);
                ch[cur][c] = sz++;
            }
            cur = ch[cur][c];
        }
        strID[id] = cur;
    }
    void getFail() {
        queue<int> q;
        for (int i = 0; i < maxChar; ++i) {
            int u = ch[0][i];
            if (u) f[u] = 0, q.push(u);
        }
        while (!q.empty()) {
            int r = q.front(); q.pop();
            for (int c = 0; c < maxChar; ++c) {
                int u = ch[r][c];
                if (!u) ch[r][c] = ch[f[r]][c];
                else f[u] = ch[f[r]][c], q.push(u);
            }
        }
    }
}

using namespace AhoCorasickAutomata;
namespace heavy_light_decomposition {
    const int maxNode = maxLen;
    struct edge *pit;
    struct edge {
        edge* next;
        int to;
        edge(edge* next = NULL, int to = 0): next(next), to(to) {}
        void* operator new(size_t) {return pit++;}
    }*first[maxNode], pool[maxNode];
    inline void addEdge(int from, int to) {
        first[from] = new edge(first[from], to);
    }
    int timestamp = 0, dfn[maxNode], s[maxNode], dep[maxNode], bel[maxNode];
    int dfs1(int u) {
        s[u] = 1, dep[u] = dep[f[u]] + 1;
        for (edge *e = first[u]; e; e = e->next)
            s[u] += dfs1(e->to);
        return s[u];
    }
    void dfs2(int u, int num) {
        bel[u] = num, dfn[u] = timestamp++;
        int mx = 0, id = -1;
        for (edge *e = first[u]; e; e = e->next)
            if (s[e->to] > mx) mx = s[id = e->to];
        if (mx == 0) return;
        dfs2(id, num);
        for (edge *e  = first[u]; e; e = e->next)
            if (e->to != id) dfs2(e->to, e->to);
    }
    int LCA(int u, int v) {
        while (bel[u] != bel[v]) {
            if (dep[bel[u]] < dep[bel[v]]) swap(u, v);
            u = f[bel[u]];
        }
        return dep[u] < dep[v] ? u : v;
    }
    void decomposition() {
        pit = pool;
        memset(first, 0, sizeof first);
        for (int i = 1; i < sz; ++i) addEdge(f[i], i);
        dfs1(0);
        dfs2(0, 0);
    }
}
using namespace heavy_light_decomposition;

inline bool cmp(const int &a, const int &b) {
    return dfn[a] < dfn[b];
}

int seq[maxLen], su[maxLen];
#define lowbit(i) ((i) & -(i))
inline void add(int x, int v) {
    for (int i = x + 1; i <= sz; i += lowbit(i)) su[i] += v;
}

inline int sum(int x) {
    int ret = 0;
    for (int i = x + 1; i > 0; i -= lowbit(i)) ret += su[i];
    return ret;
}

void solve(char *str) {
    int cur = 0, len = 0;
    for (int i = 0; str[i]; ++i) {
        int c = str[i] - 'a';
        if (!ch[cur][c]) break;
        seq[i] = cur = ch[cur][c];
        len = i + 1;
    }
    sort(seq, seq + len, cmp);
    add(dfn[seq[0]], 1);
    for (int i = 1; i < len; ++i) {
        add(dfn[seq[i]], 1);
        add(dfn[LCA(seq[i], seq[i - 1])], -1);
    }
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
#endif
    n = ReadInt();
    init();
    for (int i = 0; i < n; ++i) {
        scanf("%s", str);
        insert(str, i);
    }
    getFail();
    decomposition();
    int m = ReadInt();
    while (m--) {
        int oper = ReadInt();
        if (oper == 1) {
            scanf("%s", str);
            solve(str);
        } else {
            int x = strID[ReadInt() - 1];
            printf("%d\n", sum(dfn[x] + s[x] - 1) - sum(dfn[x] - 1));
        }
    }
    return 0;
}

BZOJ 1444 - [Jsoi2009]有趣的游戏 BZOJ 2959 - 长跑

Sengxian's Blog

BZOJ 3881 - [Coci2015]Divljak

描述

分析

代码