Description

打字機上只有28個按鍵，分別印有26個小寫英文字母和'B'、'P'兩個字母。經(jīng)阿貍研究發(fā)現(xiàn)，這個打字機是這樣工作的：

·輸入小寫字母，打字機的一個凹槽中會加入這個字母(這個字母加在凹槽的最后)。

·按一下印有'B'的按鍵，打字機凹槽中最后一個字母會消失。

·按一下印有'P'的按鍵，打字機會在紙上打印出凹槽中現(xiàn)有的所有字母并換行，但凹槽中的字母不會消失。

例如，阿貍輸入aPaPBbP，紙上被打印的字符如下：

a aa ab 我們把紙上打印出來的字符串從1開始順序編號，一直到n。打字機有一個非常有趣的功能，在打字機中暗藏一個帶數(shù)字的小鍵盤，在小鍵盤上輸入兩個數(shù)(x,y)（其中1≤x,y≤n），打字機會顯示第x個打印的字符串在第y個打印的字符串中出現(xiàn)了多少次。

阿貍發(fā)現(xiàn)了這個功能以后很興奮，他想寫個程序完成同樣的功能，你能幫助他么？

Solution

居然1A【然而看了題解】

查詢x在y中出現(xiàn)了多少次，即y的節(jié)點有多少可以通過fail跳到x的尾節(jié)點

但是這個太暴力了，于是我們建一下fail樹（fail的反向邊，由fail指針指向原節(jié)點）

轉(zhuǎn)化為查詢x的尾節(jié)點可以從fail樹到達的y的節(jié)點有多少個

然后就可以通過dfs序和樹狀數(shù)組做了

離線，對于相同的y一次性處理，標記出所有y的節(jié)點，查詢每一個x的子樹中y的節(jié)點的出現(xiàn)次數(shù)

#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<queue> #define MAXN 100005 using namespace std; int m,sz,root,pos[MAXN],in[MAXN],out[MAXN],dfn_clock=0,c[MAXN],ans[MAXN],dfn[MAXN]; int head1[MAXN],head2[MAXN],cnt1=0,cnt2=0; struct Node2 {int next,to; }e1[MAXN],e2[MAXN]; void addedge1(int u,int v) {e1[++cnt1].next=head1[u];head1[u]=cnt1;e1[cnt1].to=v; } void addedge2(int u,int v) {e2[++cnt2].next=head2[u];head2[u]=cnt2;e2[cnt2].to=v; } char s[MAXN]; struct Node1 {int next[26],par,fail; }trie[MAXN]; int newnode(int f) {trie[++sz].fail=0;trie[sz].par=f;memset(trie[sz].next,0,sizeof(trie[sz].next));return sz; } void insert() {sz=0,root=newnode(0);int i=0,p=root,_clock=0;while(s[i]){if(s[i]=='B')p=trie[p].par;else if(s[i]=='P')pos[++_clock]=p;else {int idx=s[i]-'a';if(!trie[p].next[idx])trie[p].next[idx]=newnode(p);p=trie[p].next[idx];}i++;} } queue<int>q; void build() {q.push(root);while(!q.empty()){int p=q.front();q.pop();for(int i=0;i<26;i++){int t=trie[p].fail;while(t&&!trie[t].next[i])t=trie[t].fail;if(trie[p].next[i]){trie[trie[p].next[i]].fail=t?trie[t].next[i]:root;q.push(trie[p].next[i]);}else trie[p].next[i]=t?trie[t].next[i]:root;}} } void dfs(int u) {if(dfn[u])return; ++dfn_clock;in[u]=dfn[u]=dfn_clock;for(int i=head1[u];~i;i=e1[i].next)dfs(e1[i].to);out[u]=dfn_clock; } int lowbit(int x){return x&(-x);} void add(int x,int p) {while(p<=sz+1){c[p]+=x;p+=lowbit(p);} } int query(int p) {int res=0;while(p>0){res+=c[p];p-=lowbit(p);}return res; } void solve() {int i=0,p=root,_clock=0;while(s[i]){if(s[i]=='B')add(-1,dfn[p]),p=trie[p].par;else if(s[i]=='P'){++_clock;for(int j=head2[_clock];~j;j=e2[j].next){int t=e2[j].to;ans[j]=query(out[pos[t]])-query(in[pos[t]]-1);}}else{int idx=s[i]-'a';p=trie[p].next[idx];add(1,dfn[p]);}i++;} } int main() {memset(head1,-1,sizeof(head1));memset(head2,-1,sizeof(head2));scanf("%s",s); insert(),build();for(int i=1;i<=sz;i++)addedge1(trie[i].fail,i);scanf("%d",&m);for(int i=1;i<=m;i++){int x,y;scanf("%d%d",&x,&y);addedge2(y,x);}dfs(0);solve();for(int i=1;i<=m;i++)printf("%d\n",ans[i]);return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/Zars19/p/6817784.html

總結(jié)

以上是生活随笔為你收集整理的[BZOJ 2434][Noi2011]阿狸的打字机（AC自动机+树状数组+dfs序）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。