洛谷P2414 阿狸的打字机【AC自动机】【fail树】【dfs序】【树状数组】

居然真的遇上了这种蔡队题。瑟瑟发抖。

题目背景

阿狸喜欢收藏各种稀奇古怪的东西，最近他淘到一台老式的打字机。

题目描述

打字机上只有28个按键，分别印有26个小写英文字母和'B'、'P'两个字母。经阿狸研究发现，这个打字机是这样工作的：

·输入小写字母，打字机的一个凹槽中会加入这个字母(这个字母加在凹槽的最后)。

·按一下印有'B'的按键，打字机凹槽中最后一个字母会消失。

·按一下印有'P'的按键，打字机会在纸上打印出凹槽中现有的所有字母并换行，但凹槽中的字母不会消失。

例如，阿狸输入aPaPBbP，纸上被打印的字符如下：

a aa ab 我们把纸上打印出来的字符串从1开始顺序编号，一直到n。打字机有一个非常有趣的功能，在打字机中暗藏一个带数字的小键盘，在小键盘上输入两个数(x,y)（其中1≤x,y≤n），打字机会显示第x个打印的字符串在第y个打印的字符串中出现了多少次。

阿狸发现了这个功能以后很兴奋，他想写个程序完成同样的功能，你能帮助他么？

输入输出格式

输入格式：

输入的第一行包含一个字符串，按阿狸的输入顺序给出所有阿狸输入的字符。

第二行包含一个整数m，表示询问个数。

接下来m行描述所有由小键盘输入的询问。其中第i行包含两个整数x, y，表示第i个询问为(x, y)。

输出格式：

输出m行，其中第i行包含一个整数，表示第i个询问的答案。

输入输出样例

输入样例#1：复制

aPaPBbP
3
1 2
1 3
2 3

输出样例#1：复制

2
1
0

说明

数据范围:

对于100%的数据，n<=100000,m<=100000,第一行总长度<=100000。

题意：

给n个字符串问每次有m个询问，问第x个字符串在第y个字符串中出现了几次。

思路：

最开始是暴力建树，在字符串的结尾标记序号，然后每次询问暴力在树上查找。40分TLE

后来去看题解。题解看了无敌久。

实际上我们可以发现我们每次都是沿着AC自动机的fail指针在跳，在y中匹配x就是在属于y字符串的节点中能找到多少个节点可以跳到x的结束节点。

那么我们可以把原本的边都删去只保留fail指针，这就是AC自动机上的fail树。

把fail指针的方向反过来，其实就是找以x为根的树中有多少个节点是属于y的。

但是查询有很多组，暴力查询还是不可以的。由于每次查询我们需要去标记y节点，查询完了y节点的标记要删去。所以可以考虑先把所有查询排个序，把所有y相同的放在一起进行查询。并且我们处理出查询中某个x的下标区间，当dfs过程中访问到了这个x的结束节点就同时更新这些查询的答案。

建树的过程中先记下对应序号的字符串的结束节点下标和父亲节点，遇到“B”我们就回退到父亲节点，遇到“P”就打结束标记。

然后获取fail指针，并用fail指针建边，跑一遍dfs序，得到以x为根的子树的区间。

对排好序的问题，我们预处理出所有以y为第二个参数的查询的编号区间。

用树状数组维护子树和，dfs查询子树和，当访问到y的结尾时，说明这一组y完成了打标记工作，可以去求子树和了。那么就更新一下这一组查询的答案。然后要记得将这段子树的值-1

最后重新将答案映射会原来的顺序输出。

暴力40分代码：

  1 #include <iostream>
  2 #include <set>
  3 #include <cmath>
  4 #include <stdio.h>
  5 #include <cstring>
  6 #include <algorithm>
  7 #include <vector>
  8 #include <queue>
  9 #include <map>
 10 using namespace std;
 11 typedef long long LL;
 12 #define inf 0x7f7f7f7f
 13 
 14 int n, m;
 15 const int maxn = 1e5 + 5;
 16 
 17 struct Tree{
 18     int fail;//失配指针
 19     int vis[26];//子节点位置
 20     int ed = -1;
 21 }AC[maxn];
 22 string s[maxn];
 23 int tot = 0, cnt = 0;
 24 
 25 void build(string sss, int id)
 26 {
 27     //cout<<sss<<endl;
 28     int len = sss.length();
 29     int now = 0;//字典树当前指针
 30     for(int i = 0; i < len; i++){
 31         if(AC[now].vis[sss[i] - 'a'] == 0){
 32             AC[now].vis[sss[i] - 'a'] = ++tot;
 33         }
 34         now = AC[now].vis[sss[i] - 'a'];
 35     }
 36     AC[now].ed = id;
 37 }
 38 
 39 void get_fail()
 40 {
 41     queue<int> que;
 42     for(int i = 0; i < 26; i++){
 43         if(AC[0].vis[i] != 0){
 44             AC[AC[0].vis[i]].fail = 0;
 45             que.push(AC[0].vis[i]);
 46         }
 47     }
 48     while(!que.empty()){
 49         int u = que.front();
 50         que.pop();
 51         for(int i = 0; i < 26; i++){
 52             if(AC[u].vis[i] != 0){
 53                 AC[AC[u].vis[i]].fail = AC[AC[u].fail].vis[i];
 54                 que.push(AC[u].vis[i]);
 55             }
 56             else{
 57                 AC[u].vis[i] = AC[AC[u].fail].vis[i];
 58             }
 59         }
 60     }
 61 }
 62 
 63 int AC_query(int x, int y)
 64 {
 65     int leny = s[y].length();
 66     int now = 0, ans = 0;
 67     for(int i = 0; i < leny; i++){
 68         now = AC[now].vis[s[y][i] - 'a'];
 69         for(int t = now; t; t = AC[t].fail){
 70             if(AC[t].ed == x){
 71                 ans++;
 72             }
 73         }
 74     }
 75     return ans;
 76 }
 77 
 78 int main()
 79 {
 80     string str;
 81     char tmp[maxn];
 82     cin>>str;
 83     int len = str.length(), j = 0;
 84     for(int i = 0; i < len; i++){
 85         if(str[i] == 'B'){
 86             tmp[j] = 0;
 87             j--;
 88         }
 89         else if(str[i] == 'P'){
 90 
 91             s[cnt] = tmp;
 92             //cout<<s[cnt]<<endl;
 93             build(s[cnt], cnt);cnt++;
 94         }
 95         else{
 96             tmp[j++] = str[i];
 97         }
 98     }
 99     AC[0].fail = 0;
100     get_fail();
101     scanf("%d", &m);
102     while(m--){
103         int x, y;
104         scanf("%d %d", &x, &y);
105         //cout<<s[x - 1]<<" "<<s[y - 1]<<endl;
106         cout<<AC_query(x - 1, y - 1)<<endl;
107     }
108     //cout<<s[maxid]<<endl;
109     //cout<<AC_query(s)<<endl;
110     return 0;
111 }

View Code

AC100分代码：

  1 #include <iostream>
  2 #include <set>
  3 #include <cmath>
  4 #include <stdio.h>
  5 #include <cstring>
  6 #include <algorithm>
  7 #include <vector>
  8 #include <queue>
  9 #include <map>
 10 using namespace std;
 11 typedef long long LL;
 12 #define inf 0x7f7f7f7f
 13 
 14 int n, m;
 15 const int maxn = 1e5 + 5;
 16 
 17 char ss[maxn];
 18 int nd[maxn], tot;
 19 int ans[maxn];
 20 int tree[maxn];
 21 int dfn[maxn], low[maxn], tim;
 22 int ql[maxn], qr[maxn];//dfs序左端点和右端点
 23 struct Tree{
 24     int fail, fa;
 25     int son[26];//子节点位置
 26     int vis[26];
 27     int ed = -1;
 28 }AC[maxn];
 29 struct query{
 30     int x, y, id, ans;
 31 }q[maxn];
 32 bool operator < (query a, query b){return a.y < b.y;}
 33 void update(int x, int k)
 34 {
 35     while(x <= tim){
 36         tree[x] += k;
 37         x += x & (-x);
 38     }
 39 }
 40 
 41 int sum(int x)
 42 {
 43     int ans = 0;
 44     while(x){
 45         ans += tree[x];
 46         x -= x & (-x);
 47     }
 48     return ans;
 49 }
 50 
 51 /*void build(string sss, int rt)
 52 {
 53     //cout<<sss<<endl;
 54     int len = sss.length();
 55     int now = 0;//字典树当前指针
 56     for(int i = 0; i < len; i++){
 57         if(AC[now].vis[sss[i] - 'a'] == 0){
 58             AC[now].vis[sss[i] - 'a'] = ++tot;
 59         }
 60         now = AC[now].vis[sss[i] - 'a'];
 61     }
 62     AC[now].ed = id;
 63 }*/
 64 
 65 void get_fail()
 66 {
 67     queue<int> que;
 68     for(int i = 0; i < 26; i++){
 69         if(AC[0].son[i] != 0){
 70             //AC[AC[0].vis[i]].fail = 0;
 71             que.push(AC[0].son[i]);
 72         }
 73     }
 74     while(!que.empty()){
 75         int u = que.front();
 76         que.pop();
 77         for(int i = 0; i < 26; i++){
 78             if(AC[u].son[i] != 0){
 79                 AC[AC[u].son[i]].fail = AC[AC[u].fail].son[i];
 80                 que.push(AC[u].son[i]);
 81             }
 82             else{
 83                 AC[u].son[i] = AC[AC[u].fail].son[i];
 84             }
 85         }
 86     }
 87 }
 88 
 89 struct edge{
 90     int v, nxt;
 91 }e[maxn << 1];
 92 int head[maxn], cnt = 1;
 93 void addedge(int u, int v)
 94 {
 95     e[cnt] = (edge){v, head[u]};
 96     head[u] = cnt++;
 97 }
 98 
 99 void dfs_sort(int rt)
100 {
101     dfn[rt] = ++tim;
102     for(int i = head[rt]; i; i = e[i].nxt)dfs_sort(e[i].v);
103     low[rt] = tim;
104 }
105 
106 void dfs(int rt)
107 {
108     update(dfn[rt], 1);
109     if(AC[rt].ed){
110         for(int i = ql[AC[rt].ed]; i <= qr[AC[rt].ed]; i++){
111             q[i].ans = sum(low[nd[q[i].x]]) - sum(dfn[nd[q[i].x]] - 1);
112         }
113     }
114     for(int i = 0; i < 26; i++){
115         if(AC[rt].vis[i]){
116             dfs(AC[rt].vis[i]);
117         }
118     }
119     update(dfn[rt], -1);
120 }
121 
122 int main()
123 {
124     scanf("%s", ss + 1);
125     int now = 0;
126     int len = strlen(ss + 1);
127     for(int i = 1; i <= len; i++){
128         if(ss[i] == 'B'){
129             now = AC[now].fa;
130         }
131         else if(ss[i] == 'P'){
132             nd[++n] = now;
133             AC[now].ed = n;
134         }
135         else{
136             if(!AC[now].son[ss[i] - 'a']){
137                 AC[now].son[ss[i] - 'a']= ++tot;
138                 AC[tot].fa = now;
139                 now = AC[now].son[ss[i] - 'a'];
140             }
141         }
142     }
143     for(int i = 0; i <= tot; i++){
144         for(int j = 0; j < 26; j++){
145             AC[i].vis[j] = AC[i].son[j];
146         }
147     }
148     //AC[0].fail = 0;
149     get_fail();
150     for(int i = 1; i <= tot; i++){
151         addedge(AC[i].fail, i);
152     }
153     dfs_sort(0);
154     scanf("%d", &m);
155     for(int i = 1; i <= m; i++){
156         scanf("%d %d", &q[i].x, &q[i].y);
157         q[i].id = i;
158         //cout<<s[x - 1]<<" "<<s[y - 1]<<endl;
159     }
160     sort(&q[1], &q[m + 1]);
161     for(int i = 1, pos = 1; i <= m; i = pos){
162         ql[q[i].y] = i;
163         while(q[pos].y == q[i].y) pos++;
164         qr[q[i].y] = pos - 1;
165     }
166     dfs(0);
167     for(int i = 1; i <= m; i++){
168         ans[q[i].id] = q[i].ans;
169     }
170     for(int i = 1; i <= m; i++){
171         printf("%d
", ans[i]);
172     }
173     //cout<<s[maxid]<<endl;
174     //cout<<AC_query(s)<<endl;
175     return 0;
176 }