2434: [Noi2011]阿貍的打字機

https://lydsy.com/JudgeOnline/problem.php?id=2434

分析：

　　AC自動機。

　　查詢x在y中出現了幾次，就是查詢y在AC自動機上有多少節點的可以通過fail指針指向x，反過來就是查詢fail樹上，x的子樹內有多少y的點。

　　fail樹的性質：父節點是子節點的最長的后綴。

　　然后dfs序+樹狀數組可以求，把子串y標記了，在x所對應的區間查詢即可。阿貍的打字機有一個性質，可以在掃一遍字符串的過程得到所有的字符串，所以掃一遍的過程，維護的加入刪除操作，一旦出現了一個“P”，那么前面加入的所有點就是這個串的字符。

代碼：

1 #include<cstdio> 2 #include<algorithm> 3 #include<cstring> 4 #include<iostream> 5 #include<cmath> 6 #include<cctype> 7 #include<set> 8 #include<queue> 9 #include<vector> 10 #include<map> 11 #define pa pair<int,int> 12 #define mp make_pair 13 using namespace std; 14 typedef long long LL; 15 16 inline int read() { 17 int x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1; 18 for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';return x*f; 19 } 20 21 const int N = 200005; 22 23 char s[N]; 24 vector<int> T[N]; 25 int ch[N][27], q[N], fail[N], last[N], pos[N], L[N], R[N], ans[N]; 26 int cnt, Index, Time_Index; 27 struct BIT{ 28 int n, sum[N]; 29 void update(int p,int v) { 30 for (; p <= n; p += (p & (-p))) sum[p] += v; 31 } 32 int query(int p) { 33 int ans = 0; 34 for (; p; p -= (p & (-p))) ans += sum[p]; 35 return ans; 36 } 37 int Ask(int l,int r) { 38 return query(r) - query(l - 1); 39 } 40 }bit; 41 vector< pa > Que[N]; 42 43 void Insert(char *s,int n) { 44 int u = 0; 45 for (int i = 0; i < n; ++i) { 46 if (s[i] >= 'a' && s[i] <= 'z') { 47 int c = s[i] - 'a'; 48 if (!ch[u][c]) ch[u][c] = ++Index; 49 last[ch[u][c]] = u, u = ch[u][c]; 50 } 51 else if (s[i] == 'B') u = last[u]; 52 else pos[++cnt] = u; 53 } 54 } 55 void bfs() { 56 int L = 1, R = 0; 57 for (int c = 0; c < 26; ++c) if (ch[0][c]) q[++R] = ch[0][c]; 58 while (L <= R) { 59 int u = q[L ++]; 60 T[fail[u]].push_back(u); 61 for (int c = 0; c < 26; ++c) { 62 int v = ch[u][c]; 63 if (!v) { ch[u][c] = ch[fail[u]][c]; continue; } 64 int p = fail[u]; while (p && !ch[p][c]) p = fail[p]; 65 fail[v] = ch[p][c]; 66 q[++R] = v; 67 } 68 } 69 } 70 void dfs(int u) { 71 L[u] = ++Time_Index; 72 for (int sz = T[u].size(), i = 0; i < sz; ++i) dfs(T[u][i]); 73 R[u] = Time_Index; 74 } 75 int main() { 76 scanf("%s", s); 77 int n = strlen(s); 78 Insert(s, n); 79 bfs(); 80 dfs(0); bit.n = Time_Index; // not Index || Index + 1 81 int m = read(); 82 for (int i = 1; i <= m; ++i) { 83 int x = read(), y = read(); 84 Que[y].push_back(mp(x, i)); 85 } 86 int now = 0, cnt = 0; 87 for (int i = 0; i < n; ++i) { 88 if(s[i] >= 'a' && s[i] <= 'z') 89 now = ch[now][s[i] - 'a'], bit.update(L[now], 1); 90 else if (s[i] == 'B') 91 bit.update(L[now], -1), now = last[now]; 92 else { 93 cnt ++; 94 for (int sz = Que[cnt].size(), j = 0; j < sz; ++j) { 95 int id = Que[cnt][j].second, x = Que[cnt][j].first; 96 ans[id] = bit.Ask(L[pos[x]], R[pos[x]]); 97 } 98 } 99 } 100 for (int i = 1; i <= m; ++i) printf("%d\n", ans[i]); 101 return 0; 102 }

?

轉載于:https://www.cnblogs.com/mjtcn/p/10092980.html

總結

以上是生活随笔為你收集整理的2434: [Noi2011]阿狸的打字机的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。