P2414 CF1207G

发表于 | 阅读数

$”abeaBaPcaPBP”$,给一个字符串，小写字母表示输入一个字符在一行，$P$代表打印当前字符串并且换行，$B$表示删除当前字符。$(len\leq 10^5)$

有$q$个询问，询问第$x$字符串在第$y$个字符串出现了几次。$(q\leq 10^5)$

P2414

首先可以将所以字符建立AC自动机，建立好$fail$边。

对于问题：第$x$字符串在第$y$个字符串出现了几次，因为AC自动机记录字符串前缀，暴力做法就是遍历$Y$的每个前缀，在跳$fail边$的时候是否跳到过过$x$这个字符串。

对于$fail$边，就建立$fail$树，那么问题就转换为以$x$最后一个字符为根的的$fail$子树有多少$y$的字符的节点。

如果每次询问都这么做显然复杂度过低，在让$y$节点$size+1$的过程中，其实也对其他节点(包含$y$)$+1$,由于打印性质。只需要重新再现打印过程，打出一个节点的时候$y$终点,计算它对所有$x$,$”B”建$就是删除之前节点的影响。用树状数组维护即可。

CF1207G

题意只是在原题上打字，改成$str[i]=str[x]+c$。

把询问和原来的字符串全部，建立好$fail$边，再现打印过程，只需要建立各个字符串的父子关系，跑一边$dfs$,回溯式:跑完就删除，对之后$y$计算不会产生影响。（好理解的话，就是$dfs$到某个$i$字符串终点时，只有它自己的节点是$+1$)。

代码 
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
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstring>
#include <vector>
#include <map>
using namespace std;
typedef long long ll;
#define pii pair<int, int>
#define mk make_pair
const int N = 2e5 + 10;
const int mod = 1e9 + 7;
int tr[N], dfn;
int lowbit(int x)
{
    return (-x) & x;
}
void update(int x, int w)
{
    while (x <= dfn)
    {
        tr[x] += w;
        x += lowbit(x);
    }
}
int query(int x)
{
    int res = 0;
    while (x)
    {
        res += tr[x];
        x -= lowbit(x);
    }
    return res;
}
struct node
{
    int ch[26], fa, fail;
} tri[N];
int tcnt, cnt, root, str[N];
int creat()
{
    tri[++tcnt].fa = 0;
    tri[tcnt].fail = 0;
    memset(tri[tcnt].ch, 0, sizeof(tri[tcnt].ch));
    return tcnt;
}
void insert(char *t, int len)
{
    int tmp = root;
    for (int i = 1; i <= len; i++)
    {
        if (t[i] == 'P')
            str[++cnt] = tmp;
        else if (t[i] == 'B')
            tmp = tri[tmp].fa;
        else
        {
            int k = t[i] - 'a';
            if (!tri[tmp].ch[k])
                tri[tmp].ch[k] = creat();
            tri[tri[tmp].ch[k]].fa = tmp;
            tmp = tri[tmp].ch[k];
        }
    }
}
void get_AC()
{
    queue<int> q;
    for (int i = 0; i < 26; i++)
        if (tri[root].ch[i])
        {
            int k = tri[root].ch[i];
            tri[k].fail = root;
            q.push(k);
        }
    while (!q.empty())
    {
        int x = q.front();
        q.pop();

        for (int i = 0; i < 26; i++)
        {
            int k = tri[x].ch[i];
            if (k)
            {
                tri[k].fail = tri[tri[x].fail].ch[i];
                q.push(k);
            }
            else
            {
                tri[x].ch[i] = tri[tri[x].fail].ch[i];
            }
        }
    }
}
vector<int> g[N];
vector<pii> ask[N];
char s[N];
int ld[N], rd[N], n, ans[N];
void solve(char *t, int len)
{
    int tmp = root;
    int p = 0;
    for (int i = 1; i <= len; i++)
    {
        if (t[i] == 'P')
        {
            p++;
            for (int j = 0; j < ask[p].size(); j++)
            {
                //cout << p << endl;
                int x = str[ask[p][j].first];
                ans[ask[p][j].second] = query(rd[x]) - query(ld[x] - 1);
                //cout << x << endl;
            }
        }
        else if (t[i] == 'B')
            update(ld[tmp], -1), tmp = tri[tmp].fa;
        else
        {
            int k = t[i] - 'a';
            tmp = tri[tmp].ch[k];
            update(ld[tmp], 1);
            //cout << tmp << endl;
        }
    }
}
void dfs(int x)
{
    ld[x] = ++dfn;
    for (int i = 0; i < g[x].size(); i++)
    {
        int to = g[x][i];
        dfs(to);
    }
    rd[x] = dfn;
}
int main()
{
    scanf("%s", s + 1);
    insert(s, strlen(s + 1));
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        ask[y].push_back(mk(x, i));
    }
    get_AC();
    //cout << tcnt << endl;
    // for (int i = 1; i <= tcnt; i++)
    //     cout << i << " " << tri[i].fail << " ";
    for (int i = 1; i <= tcnt; i++)
        g[tri[i].fail].push_back(i);
    dfs(0);
    //cout << ld[3] << endl;
    solve(s, strlen(s + 1));
    for (int i = 1; i <= n; i++)
        printf("%d\n", ans[i]);
}
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
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstring>
#include <vector>
#include <map>
using namespace std;
typedef long long ll;
#define pii pair<int, int>
#define mk make_pair
const int N = 8e5 + 10;
const int mod = 1e9 + 7;
int tr[N], dfn;
int lowbit(int x)
{
    return (-x) & x;
}
void update(int x, int w)
{
    while (x <= dfn)
    {
        tr[x] += w;
        x += lowbit(x);
    }
}
int query(int x)
{
    int res = 0;
    while (x)
    {
        res += tr[x];
        x -= lowbit(x);
    }
    return res;
}
struct node
{
    int ch[26], fa, fail;
} tri[N];
int tcnt, cnt, root, str[N], q[N];
int creat()
{
    tri[++tcnt].fa = 0;
    tri[tcnt].fail = 0;
    memset(tri[tcnt].ch, 0, sizeof(tri[tcnt].ch));
    return tcnt;
}
int ins(int tmp, int k)
{
    if (!tri[tmp].ch[k])
        tri[tmp].ch[k] = creat();
    return tri[tmp].ch[k];
}
void insert(char *t, int len, int id)
{
    int tmp = root;
    for (int i = 1; i <= len; i++)
    {
        int k = t[i] - 'a';
        if (!tri[tmp].ch[k])
            tri[tmp].ch[k] = creat();
        tmp = tri[tmp].ch[k];
    }
    q[id] = tmp;
}
void get_AC()
{
    queue<int> q;
    for (int i = 0; i < 26; i++)
        if (tri[root].ch[i])
        {
            int k = tri[root].ch[i];
            tri[k].fail = root;
            q.push(k);
        }
    while (!q.empty())
    {
        int x = q.front();
        q.pop();

        for (int i = 0; i < 26; i++)
        {
            int k = tri[x].ch[i];
            if (k)
            {
                tri[k].fail = tri[tri[x].fail].ch[i];
                q.push(k);
            }
            else
            {
                tri[x].ch[i] = tri[tri[x].fail].ch[i];
            }
        }
    }
}
vector<int> g[N], g1[N];
vector<pii> ask[N];
char s[N], ss[N];
int ld[N], rd[N], n, ans[N], en[N], m, f[N], fa[N];

void dfs(int x)
{
    ld[x] = ++dfn;
    for (int i = 0; i < g[x].size(); i++)
    {
        int to = g[x][i];
        dfs(to);
    }
    rd[x] = dfn;
}
void solve(int x)
{
    //cout << x << endl;
    update(ld[en[x]], 1);
    int y = x;
    for (int i = 0; i < ask[y].size(); i++)
    {
        int p = q[ask[y][i].first];
        ans[ask[y][i].second] = query(rd[p]) - query(ld[p] - 1);
    }
    for (int i = 0; i < g1[x].size(); i++)
        solve(g1[x][i]);
    update(ld[en[x]], -1);
}
int main()
{

    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        int p, x;
        char c;
        scanf("%d", &p);
        if (p == 1)
        {
            scanf(" %c ", &c);
            en[i] = ins(root, c - 'a');

            f[en[i]] = i;
        }
        else
        {
            scanf("%d %c ", &x, &c);
            fa[i] = x;
            en[i] = ins(en[x], c - 'a');
            f[en[i]] = i;
        }
        g1[fa[i]].push_back(i);
    }
    scanf("%d", &m);
    for (int i = 1; i <= m; i++)
    {
        int y;
        scanf("%d %s", &y, s + 1);
        insert(s, strlen(s + 1), i);
        ask[y].push_back(mk(i, i));
    }
    get_AC();

    for (int i = 1; i <= tcnt; i++)
        g[tri[i].fail].push_back(i);
    dfs(0);
    solve(root);
    //cout << ld[3] << endl;

    for (int i = 1; i <= m; i++)
        printf("%d\n", ans[i]);
}