0%

「NOI2011」阿狸的打字机

发表于 更新于 阅读次数： Valine：

题目链接

首先我们发现按这个样子生成字符串的话总长可能很长，但是它们所构成的trie树节点个数最多只有 \(n+1\) 个，这样的话我们考虑在trie树上来做这个问题。

发现这是一个字符串匹配问题，单纯的trie肯定是很难处理，所以我们把trie建成AC自动机。我们考虑AC自动机fail边的含义，它实际上指向了这个节点的存在于这个trie树中的最长的真后缀，那么如果字符串 \(x\) 在 \(y\) 的某一位出现（设这位为 \(c\) 则 \(x\) 是 \(y[1,c]\) 的后缀）我们从这一位在AC自动机上对应的节点一直跳fail，那么一定是可以跳到 \(x\) 的终止节点的。换句话说，这一位的节点在fail树中 \(x\) 的子树内。

这样的话我们就有了一个暴力算法，对于每组询问，我们把 \(y\) 的所有前缀代表的节点都打上标记，然后询问 \(x\) 在fail树的子树内有多少标记。

（从现在开始请注意trie树和fail树的区别）我们考虑优化，首先我们可以把询问离线下来，对于 \(y\) 相同的一起处理。具体地，我们计算出fail树的dfs序，那么 \(x\) 在fail中的子树对应了一段dfs序的区间。我们用树状数组维护单点修改标记和区间查询就可以了。但是这样对于每一个 \(y\) 还是要暴力跳前缀，复杂度还是不对，怎么办？我们只需要在trie树上dfs（注意这里是trie树！而之前和一会说的dfs序都是fail树的！），当一个节点进栈时给其fail树的dfs这个位置加上1，然后处理这个点的询问（我们给每个点开个桶，对于每个询问把它扔到 \(y\) 的终止节点的桶里），出栈时再-1，这样的话复杂度就是 \(O(n\log n)\) 的了。加减询问仍旧用一个树状数组就好了。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include<bits/stdc++.h>
using namespace std;
int ch[100005][26],fail[100005],fa[100005],ed[100005],cnt,
target[100005],pre[100005],last[100005],tot,dfn[100005],
tree[100005],ans[100005],c,er[100005];
void mod(int x,int y)
{
    for(int i=x;i<=cnt+2;i+=(i&(-i)))tree[i]+=y;
}
int ask(int x)
{
    int res=0;
    for(int i=x;i;i-=(i&(-i)))res+=tree[i];
    return res;
}
string str;
queue<int>q;
struct query{int x,y,id;};
vector<query>v[100005];
vector<int>to[100005];
void bfs()
{
    for(int i=0;i<=25;i++)if(ch[0][i])q.push(ch[0][i]);
    while(!q.empty())
    {
        int now=q.front();
        q.pop();
        for(int i=0;i<=25;i++)
        {
            if(ch[now][i])fail[ch[now][i]]=ch[fail[now]][i],q.push(ch[now][i]);
            else ch[now][i]=ch[fail[now]][i];
        }
    }
}
void add(int x,int y)
{
    target[++tot]=y;
    pre[tot]=last[x];
    last[x]=tot;
}
void dfs(int x)
{
    dfn[x]=++c;
    for(int i=last[x];i;i=pre[i])dfs(target[i]);
    er[x]=c;
}
void dfs2(int x)
{
    mod(dfn[x],1);
    for(auto tar:to[x])dfs2(tar);
    for(int i=0;i<v[x].size();i++)
        ans[v[x][i].id]=ask(er[ed[v[x][i].x]])
                       -ask(dfn[ed[v[x][i].x]]-1);
    mod(dfn[x],-1);
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>str;
    int n=str.size(),m=0,now=0;
    for(int i=0;i<n;i++)
    {
        if(str[i]=='B')now=fa[now];
        else if(str[i]=='P')ed[++m]=now;
        else
        {
            int c=str[i]-'a';
            if(!ch[now][c])ch[now][c]=++cnt,fa[ch[now][c]]=now;
            now=ch[now][c];
        }
    }
    for(int i=0;i<=cnt;i++)
        for(int k=0;k<=25;k++)
            if(ch[i][k])to[i].push_back(ch[i][k]);
    bfs();
    for(int i=1;i<=cnt;i++)add(fail[i],i);
    int q;
    cin>>q;
    for(int i=1;i<=q;i++)
    {
        query t;
        cin>>t.x>>t.y;
        t.id=i;
        v[ed[t.y]].push_back(t);
    }
    dfs(0);
    dfs2(0);
    for(int i=1;i<=q;i++)cout<<ans[i]<<endl;
    return 0;
}