LOJ #2444 「NOI2011」阿狸的打字机

zrzring 2020-06-14 PM 25℃ 0条

之后决定loj有的题就跑loj测并写loj下的题解了,loj评测机真的太nb了

按题意把这些东西扔到AC自动机上,然后对于询问,根据字串可以表示为前缀的后缀这一条性质,在AC自动机上的fail跳的是后缀,于是我们就看y串的哪些前缀跳fail能跳到表示x串的末尾的点就行了

显然T飞了,考虑优化,fail树是一个常用的套路,容易发现这样问题转换成了在fail树上找x串的末尾这个点,其子树里有多少y串上的点就好了

但是好像还是$O(n^2)$的,考虑将AC自动机分成fail树和trie树,这样我们求出fail树上的dfn,我们知道每个点的子树的dfn一定是这个点的dfn后size位,然后对trie树做一遍dfs,并对经过的点用树状数组维护,每次到一个单词的末尾的时候,因为是对trie树dfs,所以仅有目前这个单词的所有点被经过了,于是就可以求这个单词作为y串的询问了

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
#define lowbit(x) (x & -x)
#define inf 1e9
using namespace std;
void file() {
    freopen("read.in", "r", stdin);
    freopen("write.out", "w", stdout);
}
const int N = 2e5 + 10;
inline int read() {
    int sym = 0, res = 0; char ch = getchar();
    while (!isdigit(ch)) sym |= (ch == '-'), ch = getchar();
    while (isdigit(ch)) res = (res << 3) + (res << 1) + (ch ^ 48), ch = getchar();
    return sym ? -res : res;
}
struct EDGE {
    int u, v, nxt;
} edge[N];
int n, m, fa[N], num[N], cnt, ncnt, son[N][30], fail[N], dfn[N], siz[N];
int head[N], x[N], y[N], ans[N], tsum[N], trie[N][30], fin[N];
char ch[N];
vector <int> q[N];
void modify(int x, int t) {
    for (; x <= cnt; x += lowbit(x)) tsum[x] += t;
}
int query(int x) {
    int res = 0;
    for (; x; x -= lowbit(x)) res += tsum[x];
    return res;
}
void add(int u, int v) {
    edge[++cnt] = (EDGE){u, v, head[u]}; head[u] = cnt;
} 
void ins(char *ch) {
    int len = strlen(ch), u = 0;
    for (int i = 0; i < len; i++) {
        if (ch[i] == 'B') {u = fa[u]; continue;}
        if (ch[i] == 'P') {num[++ncnt] = u; fin[u] = 1; continue;}
        int v = ch[i] - 'a';
        if (!son[u][v]) trie[u][v] = son[u][v] = ++cnt, fa[cnt] = u;
        u = son[u][v];
    }
}
void dfs1(int u) {
    dfn[u] = ++cnt; siz[u] = 1;
    for (int e = head[u]; e; e = edge[e].nxt) {
        int v = edge[e].v; dfs1(v); siz[u] += siz[v];
    }
}
void build() {
    queue <int> q;
    for (int i = 0; i < 26; i++) {
        if (son[0][i]) q.push(son[0][i]);
    }
    while (!q.empty()) {
        int u = q.front(); q.pop(); add(fail[u], u);
        for (int i = 0; i < 26; i++) {
            int v = son[u][i];
            if (v) fail[v] = son[fail[u]][i], q.push(v);
            else son[u][i] = son[fail[u]][i];
        }
    }
}
void dfs2(int u) {
    modify(dfn[u], 1);
    vector <int> :: iterator it;
    if (fin[u]) {
        for (it = q[u].begin(); it != q[u].end(); it++) {
            int i = *it;
            ans[i] = query(dfn[num[x[i]]] + siz[num[x[i]]] - 1) - query(dfn[num[x[i]]] - 1);
        }
    }
    for (int i = 0; i < 26; i++) {
        if (trie[u][i]) dfs2(trie[u][i]);
    }
    modify(dfn[u], -1);
}
int main() {
    scanf("%s", ch); ins(ch); cnt = 0; build(); cnt = 0; dfs1(0);
    n = read();
    for (int i = 1; i <= n; i++) {
        x[i] = read(); y[i] = read(); q[num[y[i]]].push_back(i);
    }
    dfs2(0);
    for (int i = 1; i <= n; i++) printf("%d\n", ans[i]);
    return 0;
}

评论


您还没有登录呦


登录 注册
Title - Artist
0:00