首页 > 代码库 > BZOJ 2434 NOI 2011 阿狸的打字机 AC自动机构造fail树
BZOJ 2434 NOI 2011 阿狸的打字机 AC自动机构造fail树
题目大意:有一种打字机上有28个字母,分别是26个小写字母和BP,其中B代表退格,P代表换行,每一行就是一个字符串。现在给这些字符串标号,并询问x串在y串中出现过几次。
思路:这算是NOI史上最难的字符串的题了吧(动物园)。
首先按照题意不难建一个AC自动机出来,按照正常的思路,对于每一个询问都需要在AC自动机上暴力的查找。但这样时间会十分好看。
于是我们想,fail指针构成的一定是一棵树,将这颗树的DFS序搞出来的话会有非常好的性质--串中存在某个字串的一定在这个字串的子树中,也就是对应DFS序的一段区间里。这样我们吧所有询问离线,对整个trie树进行一次深搜,用fenwick来维护DFS序中的情况,顺便处理出来答案。
CODE:
#include <queue> #include <vector> #include <cstdio> #include <cctype> #include <cstring> #include <iostream> #include <algorithm> #define MAX 100010 using namespace std; #define P(a) ((a) - 'a') struct Trie{ Trie *son[26],*fail; int end; Trie() { memset(son,NULL,sizeof(son)); fail = NULL; } }mempool[MAX],*C = mempool + 1,*root = C++; int asks; int fenwick[MAX]; int head[MAX],total; int next[MAX],aim[MAX]; int pos[MAX],p[MAX]; pair<int,int> range[MAX]; vector<pair<int,int> > G[MAX]; int ans[MAX]; inline void Add(int x,int y) { next[++total] = head[x]; aim[total] = y; head[x] = total; } void BuildTrie() { static Trie *stack[MAX],*now = root; int top = 0,cnt = 0; char c; stack[++top] = root; while(c = getchar(),isalpha(c)) { if(c == 'P') { now->end = ++cnt; p[now - mempool] = cnt; } else if(c == 'B') now = stack[top--]; else { stack[++top] = now; if(now->son[P(c)] == NULL) now->son[P(c)] = C++; now = now->son[P(c)]; } } } void BuildACAutomation() { static queue<Trie *> q; while(!q.empty()) q.pop(); q.push(root); while(!q.empty()) { Trie *now = q.front(); q.pop(); for(int i = 0; i < 26; ++i) { if(now->son[i] == NULL) continue; if(now == root) { now->son[i]->fail = root; Add(root - mempool,now->son[i] - mempool); } else { Trie *temp = now->fail; while(temp != root && temp->son[i] == NULL) temp = temp->fail; if(temp->son[i] != NULL) temp = temp->son[i]; now->son[i]->fail = temp; Add(temp - mempool,now->son[i] - mempool); } q.push(now->son[i]); } } } void Pre(int x) { static int k = 0; pos[x] = ++k; if(p[x]) range[p[x]].first = k; for(int i = head[x]; i; i = next[i]) Pre(aim[i]); if(p[x]) range[p[x]].second = k; } inline void Fix(int x,int c) { for(; x < MAX; x += x&-x) fenwick[x] += c; } inline int GetSum(int x) { int re = 0; for(; x; x -= x&-x) re +=fenwick[x]; return re; } void DFS(int x) { Trie *now = &mempool[x]; if(pos[x]) Fix(pos[x],1); for(vector<pair<int,int> >::iterator it = G[p[x]].begin(); it != G[p[x]].end(); ++it) { pair<int,int> now = *it; ans[now.second] = GetSum(range[now.first].second) - GetSum(range[now.first].first - 1); } for(int i = 0; i < 26; ++i) if(now->son[i] != NULL) DFS(now->son[i] - mempool); if(pos[x]) Fix(pos[x],-1); } int main() { BuildTrie(); BuildACAutomation(); cin >> asks; for(int x,y,i = 1; i <= asks; ++i) { scanf("%d%d",&x,&y); G[y].push_back(make_pair(x,i)); } Pre(1); DFS(1); for(int i = 1; i <= asks; ++i) printf("%d\n",ans[i]); return 0; } ?
BZOJ 2434 NOI 2011 阿狸的打字机 AC自动机构造fail树
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。