首页 > 代码库 > bzoj2434

bzoj2434

2024-11-03 05:25:01   205人阅读

ac自动机+bit

很早以前就做过这道题了，再做一遍。

构建ac自动机的话就是模拟一下就可以了，然后就是如何统计答案。

这里巧妙地利用了fail树的性质，fail树是指当前在trie上从根到这个节点的路径，也就是某个单词的前缀，这个单词的前缀的后缀能够匹配上另一个单词的前缀，于是就把fail指针连向那个单词的前缀最后的节点。

fail树的根就是ac自动机的根。

如果我们用一个模式串来匹配单词，那么fail指针就能够统计当前前缀的后缀的单词的数量，如果不能继续匹配下去，就沿着fail指针走。

这道题利用了fail树的性质，统计x在y中出现多少次，就是说从根到y的路径中有多少个节点的fail指向x，也就是说有多少位置的后缀是x单词，fail指针总是指向一个是当前后缀的前缀，而前缀就是一个单词。

直接暴力是不行的，那么我们对于询问分类，把每个x用邻接表存在对应的y下，然后求出fail树的dfs序，按照建自动机的方式模拟，每插入完一个单词，就统计这个单词对应的询问，统计询问是利用树状数组，每走到一个节点就把这个节点的dfs序插入bit，离开就删除，这样就保证bit里总是只存在当前的单词，走到打印的地方时，这个单词的所有节点就都插入在bit里了，也不会有其他多余的单词，所以每次统计询问单词的子树和就行了，因为我们是查询y单词有多少节点的fail指针指向x，那么把fail树反向，也就是说有多少y单词上的节点在x的子树里，因为fail指针能够构成一棵树，并且是有方向的，只有一个单词的后缀指向前缀才会后构成fail指针，所以对于一个单词，fail指针的反向也就统计了一个单词出现在其他单词的次数。

技术分享 
#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int N = 100010;
int n, m;
vector<int> g[N];
vector<PII> G[N];
int ans[N];
char s[N];
struct BIT {
    int tree[N];
    int lowbit(int i) { return i & (-i); }
    void update(int pos, int delta)
    {
        for(int i = pos; i <= n; i += lowbit(i)) tree[i] += delta;
    }
    int query(int pos)
    {
        int ret = 0;
        for(int i = pos; i; i -= lowbit(i)) ret += tree[i];
        return ret;
    }
} t;
struct AC {
    int root, Time, tot, cnt;
    int child[N][26], fail[N], pos[N], mir[N], st[N], fi[N], fa[N];
    void construct(char s[])
    {
        int now = root;
        for(int i = 1; i <= n; ++i)
        {
            if(s[i] >= ‘a‘ && s[i] <= ‘z‘)
            {
                if(!child[now][s[i] - ‘a‘])
                    child[now][s[i] - ‘a‘] = ++cnt;
                fa[child[now][s[i] - ‘a‘]] = now;
                now = child[now][s[i] - ‘a‘];
            }
            else if(s[i] == ‘B‘) now = fa[now];
            else 
            {
                pos[now] = ++tot;
                mir[tot] = now;
            }
        }
    }
    void get_fail()
    {
        queue<int> q;
        q.push(root);
        while(!q.empty())
        {
            int u = q.front();
            q.pop();
            for(int i = 0; i < 26; ++i) if(child[u][i])
            {
                int v = child[u][i];
                if(u == root) fail[v] = root;
                else
                {
                    int now = fail[u];
                    while(now != root && !child[now][i]) now = fail[now];
                    fail[v] = child[now][i];
                }
                g[v].push_back(fail[v]);
                g[fail[v]].push_back(v);
                q.push(v);
            }
        }
    }
    void solve()
    {
        int now = root;
        for(int i = 1; i <= n; ++i)
        {
            if(s[i] == ‘P‘)
            {
                for(int j = 0; j < G[pos[now]].size(); ++j)
                {
                    PII x = G[pos[now]][j];
                    int u = mir[x.first], id = x.second;
                    ans[id] += t.query(fi[u]) - t.query(st[u] - 1); 
                }
            } 
            else if(s[i] == ‘B‘) 
            {
                t.update(st[now], -1);
                now = fa[now];
            }
            else
            {
                now = child[now][s[i] - ‘a‘];
                t.update(st[now], 1);
            }
        }
    }
    void dfs(int u, int last)
    {
        st[u] = ++Time;
        for(int i = 0; i < g[u].size(); ++i)
        {
            int v = g[u][i];
            if(v == last) continue;
            dfs(v, u);
        }
        fi[u] = Time;
    }
} ac;
int main()
{
    scanf("%s", s + 1);
    n = strlen(s + 1);
    ac.construct(s);
    ac.get_fail();
    ac.dfs(0, -1);
    scanf("%d", &m);
    for(int i = 1; i <= m; ++i)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        G[y].push_back(make_pair(x, i));
    }
    ac.solve();
    for(int i = 1; i <= m; ++i) printf("%d\n", ans[i]);
    return 0;
}
View Code

 

bzoj2434


联系
我们