CF-1207

Posted on | Edited on | In | Views:

G. Indie Album

题意

有 $n$ 个字符串,对于第 $i$ 个字符串通过以下两种方式中的一个给出。

  1. $1 c$，该字符串只含一个字符 $c$ 。
  2. $2 x c$ ,该字符串为第 $x(1\le x<i)$ 个字符串末尾添加一个字符 $c$ 得到。

有 $m$ 次询问，每次询问给出一个字符串 $s$ 和位置编号 $x$,问在上述第 $x$ 个字符串中，字符串 $s$ 出现了几次。

题解

对询问构建 $AC$自动机，因为文本串是树形结构，我们可以跑一个 $dfs$ 枚举所有文本串，每次都添加一个字符，当回溯回去的时候删除这个字符对答案的贡献。

因为每个匹配串在文本串中出现的次数为将文本串在 $AC$自动机上跑一遍并将走到的位置权值 $+1$，该字符串所对应的 $fail$ 节点的子树权值和。所以我们拎出 $fail$ 树，对其 $dfs$ 序构造树状数组。

代码

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
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
#include <bits/stdc++.h>
using namespace std;
#define forl(i, l, r) for (int i = l; i <= r; i++)
#define forr(i, r, l) for (int i = r; i >= l; i--)
#define for1(i, n) for (int i = 1; i <= n; i++)
#define fro1(i, n) for (int i = 1; i <= n; i++)
#define for0(i, n) for (int i = 0; i < n; i++)
#define fro0(i, n) for (int i = 0; i < n; i++)
#define meminf(a) memset(a, inf, sizeof(a))
#define mem_1(a) memset(a, -1, sizeof(a))
#define mem0(a) memset(a, 0, sizeof(a))
#define memcp(a,b) memcpy(a,b,sizeof(b))
#define oper(type) bool operator <(const type y)const
#define mp make_pair
#define pu_b push_back
#define pu_f push_front
#define po_b pop_back
#define po_f pop_front
#define fi first
#define se second
#define whiel while
#define retrun return
typedef pair<long long, long long> pll;
typedef vector<long long> vll;
typedef pair<int, int> pii;
typedef unsigned long long ull;
typedef vector<int> vii;
typedef double db;
typedef long double ldb;
typedef long long ll;
typedef int itn;
void in(initializer_list<int*> li){for(auto ptr=li.begin();ptr!=li.end();ptr++)scanf("%d",*ptr);}
void in(initializer_list<ll*> li){for(auto ptr=li.begin();ptr!=li.end();ptr++)scanf("%lld",*ptr);}
void in(initializer_list<db*> li){for(auto ptr=li.begin();ptr!=li.end();ptr++)scanf("%lf",*ptr);}
void out(initializer_list<int> li){auto ti=li.end();ti--;for(auto ptr=li.begin();ptr!=li.end();ptr++)printf("%d%c",*ptr,ptr==ti?'\n':' ');}
void out(initializer_list<ll> li){auto ti=li.end();ti--;for(auto ptr=li.begin();ptr!=li.end();ptr++)printf("%lld%c",*ptr,ptr==ti?'\n':' ');}
void out(initializer_list<db> li){auto ti=li.end();ti--;for(auto ptr=li.begin();ptr!=li.end();ptr++)printf("%f%c",*ptr,ptr==ti?'\n':' ');}
void out(int a,bool ln){printf("%d%c",a,ln?'\n':' ');}
void out(ll a,bool ln){printf("%lld%c",a,ln?'\n':' ');}
void out(db a,int digit,bool ln){printf("%.*f%c",digit,a,ln?'\n':' ');}
void out(ldb a,int digit,bool ln){printf("%.*Lf%c",digit,a,ln?'\n':' ');}
void out0(int a[],int n){for0(i,n)out(a[i],i==n-1);}
void out1(int a[],int n){for1(i,n)out(a[i],i==n);}
void out0(ll a[],int n){for0(i,n)out(a[i],i==n-1);}
void out1(ll a[],int n){for1(i,n)out(a[i],i==n);}
int in(int &a,int &b,int &c,int &d){return scanf("%d%d%d%d",&a,&b,&c,&d);}
int in(int &a,int &b,int &c){return scanf("%d%d%d",&a,&b,&c);}
int in(int &a,int &b){return scanf("%d%d",&a,&b);}
int in(ll &a,ll &b,ll &c,ll &d){return scanf("%lld%lld%lld%lld",&a,&b,&c,&d);}
int in(ll &a,ll &b,ll &c){return scanf("%lld%lld%lld",&a,&b,&c);}
int in(ll &a,ll &b){return scanf("%lld%lld",&a,&b);}
int in(ll &a){return scanf("%lld",&a);}
int in(int &a){return scanf("%d",&a);}
int in(char *s){return scanf("%s",s);}
int in(char &c){return scanf("%c",&c);}
int in(db &a){return scanf("%lf",&a);}
int in(ldb &a){return scanf("%Lf",&a);}
void in0(int a[],int n){for0(i,n)in(a[i]);}
void in1(int a[],int n){for1(i,n)in(a[i]);}
void in0(ll a[],int n){for0(i,n)in(a[i]);}
void in1(ll a[],int n){for1(i,n)in(a[i]);}
const db pi = acos(-1);
const db eps = 1e-8;
int sign(db a) {return a < -eps ? -1 : a > eps;}
int db_cmp(db a, db b){ return sign(a-b);}
ll inf =0x3f3f3f3f;
ll mod = 1e9+7;
const int M = 2.1e5;
const int N = 4.1e5;
/*-----------------------------------head----------------------------------------------*/
 
const int MAX = 26;
int tot;
vii failTree[N];
struct Node {
    int id;
    Node *Next[MAX];
    Node *Fail;  //失配指针,类似next数组,最大的next是和自身比较,fail是和其它匹配串比较
    Node() {
        memset(Next, 0, sizeof(Next));
        Fail = 0;
        id=tot++;
    }
} * root,*pp;
int Insert(char s[]) {
    Node *p = root;
    int len=strlen(s);
    for(int i=0;i< len;i++) {
        int c = s[i] - 'a';
        if (p->Next[c] == NULL) {
            Node *newnode = new Node;
            p->Next[c] = newnode;
            p = newnode;
        } else
            p = p->Next[c];
    }
    return p->id;
}
void BuildFail() {
    queue<Node *> que;
    root->Fail=root;
    for(int i=0;i<26;i++){
        if(root->Next[i]){
            root->Next[i]->Fail=root;
            que.push(root->Next[i]);
        }else root->Next[i]=root;
    }
    while (!que.empty()) {
        Node *p = que.front();
        que.pop();
        failTree[p->Fail->id].pu_b(p->id);
        for(int i=0;i<26;i++){
            if(p->Next[i]){
                p->Next[i]->Fail=p->Fail->Next[i];
                que.push(p->Next[i]);
            }else p->Next[i]=p->Fail->Next[i];
        }
    }
}
int L[N],R[N],cnt;
void Dfs(int rt){
    L[rt]=cnt++;
    for(int v:failTree[rt]){
        Dfs(v);
    }
    R[rt]=cnt-1;
}
int sum[N];
void add(int p,int x,int n){ //a[p]+=x,数组为[1,n]
    while(p&&p<=n)sum[p]+=x,p+=p&-p;
}
ll query(int p){
    ll ans = 0;
    while(p)ans+=sum[p],p-=p&-p;
    return ans;
}
struct NODE{
    char c;
    vector<pii> v;
}a[N];
 
vii node[N];
char s[N];
int ans[N];
void dfs(int rt){
    for(int v:node[rt]){
        Node *tmp=pp;
        pp = pp->Next[c-'a'];
        add(L[pp->id],1,cnt-1);
        for(auto i:a[v].v)ans[i.se]=query(R[i.fi])-query(L[i.fi]-1);
        dfs(v);
        add(L[pp->id],-1,cnt-1);
        pp=tmp;
    }
}
int main() {
    int n,m,tp,v;
    root = new Node;
    pp=root;
    in(n);
    for1(i,n){
        in(tp);
        if(tp==1){
            in(s);
            node[0].pu_b(i);
        }else{
            in(v);in(s);
            node[v].pu_b(i);
        }
        a[i].c=s[0];
    }
    in(m);
    for1(i,m){
        in(v);in(s);
        a[v].v.pu_b(pii(Insert(s),i));
    }
    BuildFail();
    Dfs(0);
    dfs(0);
    for1(i,m)out(ans[i],1);
    return 0;
}