题目描述
打字机上只有28个按键，分别印有26个小写英文字母和'B'、'P'两个字母。经阿狸研究发现，这个打字机是这样工作的：
·输入小写字母，打字机的一个凹槽中会加入这个字母(这个字母加在凹槽的最后)。
·按一下印有'B'的按键，打字机凹槽中最后一个字母会消失。
·按一下印有'P'的按键，打字机会在纸上打印出凹槽中现有的所有字母并换行，但凹槽中的字母不会消失。
例如，阿狸输入aPaPBbP，纸上被打印的字符如下：
a aa ab 我们把纸上打印出来的字符串从1开始顺序编号，一直到n。打字机有一个非常有趣的功能，在打字机中暗藏一个带数字的小键盘，在小键盘上输入两个数(x,y)（其中1≤x,y≤n），打字机会显示第x个打印的字符串在第y个打印的字符串中出现了多少次。
阿狸发现了这个功能以后很兴奋，他想写个程序完成同样的功能，你能帮助他么？
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~·
这道题是fail树的裸题。利用ac自动机或trie图能构建出trie树上的fail指针，代表与其拥有最长相同后缀的、比他短的位置。
重点是每个点只有唯一的fail指针。
这就很像树了。（每个点只有唯一的父节点）
所以我们可以将fail指针反指，形成一棵树，叫fail树。
fail树所具有的性质就是：当前子树中所有点代表的前缀都以当前树根代表的字符串为后缀。
人话翻译：
假设每个点对应一个字符串，那么若b点在a点的子树中，a一定是b的后缀。
现在再来看这道题，问题是求一个子串中有多少个另一个子串，就是问这个子串中的所有前缀以另一串为后缀的有多少个。
于是上fail树：
#include<queue> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define N 100050 int n,m,len,tot,rt[N],hed[N],cnt; char s[N]; struct Trie { int ch[28]; int fa,fl; }tr[N]; struct EG { int to,nxt; }e[N]; void ae(int f,int t) { e[++cnt].to = t; e[cnt].nxt = hed[f]; hed[f] = cnt; } void trie_pic() { queue<int>q; for(int i=1;i<=26;i++) if(tr[0].ch[i]) q.push(tr[0].ch[i]),ae(0,tr[0].ch[i]); while(!q.empty()) { int u = q.front(); q.pop(); for(int i=1;i<=26;i++) { int &v = tr[u].ch[i]; if(!v) { v = tr[tr[u].fl].ch[i]; continue; } tr[v].fl = tr[tr[u].fl].ch[i]; ae(tr[v].fl,v); q.push(v); } } } int tin[N],tout[N],tim; void dfs(int u) { tin[u]=++tim; for(int j=hed[u];j;j=e[j].nxt)dfs(e[j].to); tout[u]=tim; } int f[2*N]; void up(int x,int d) { if(!x)return ; while(x<=200000) { f[x]+=d; x+=(x&(-x)); } } int down(int x) { if(!x)return 0; int ret = 0; while(x) { ret+=f[x]; x-=(x&(-x)); } return ret; } struct node { int u,v,id; }p[N]; int ans[N]; bool cmp(node a,node b) { return a.v<b.v; } int main() { scanf("%s",s+1); len = strlen(s+1); int u = 0; for(int i=1;i<=len;i++) { if(s[i]>='a'&&s[i]<='z') { int c = s[i]-'a'+1; if(!tr[u].ch[c])tr[u].ch[c]=++tot,tr[tot].fa=u; u=tr[u].ch[c]; }else if(s[i]=='B') { u = tr[u].fa; }else { rt[++n] = u; } } trie_pic(); dfs(0); scanf("%d",&m); for(int i=1;i<=m;i++)scanf("%d%d",&p[i].u,&p[i].v),p[i].id=i; sort(p+1,p+1+m,cmp); int k = 1,c = 0; u = 0; for(int i=1;i<=len;i++) { if(s[i]>='a'&&s[i]<='z') { int c = s[i]-'a'+1; u = tr[u].ch[c]; up(tin[u],1); }else if(s[i]=='B') { up(tin[u],-1); u = tr[u].fa; }else { c++; while(p[k].v==c) { ans[p[k].id] = down(tout[rt[p[k].u]])-down(tin[rt[p[k].u]]-1); k++; } } } for(int i=1;i<=m;i++)printf("%d ",ans[i]); return 0; }