[NOI2011]阿狸的打字机（好题！！！！）

2785: [NOI2011]阿狸的打字机

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 7  Solved: 3
[Submit][Status][Web Board]

Description

阿狸喜欢收藏各种稀奇古怪的东西，最近他淘到一台老式的打字机。打字机上只有28个按键，分别印有26个小写英文字母和'B'、'P'两个字母。
经阿狸研究发现，这个打字机是这样工作的：
l 输入小写字母，打字机的一个凹槽中会加入这个字母(这个字母加在凹槽的最后)。
l 按一下印有'B'的按键，打字机凹槽中最后一个字母会消失。
l 按一下印有'P'的按键，打字机会在纸上打印出凹槽中现有的所有字母并换行，但凹槽中的字母不会消失。
例如，阿狸输入aPaPBbP，纸上被打印的字符如下：
a
aa
ab
我们把纸上打印出来的字符串从1开始顺序编号，一直到n。打字机有一个非常有趣的功能，在打字机中暗藏一个带数字的小键盘，在小键盘上输入两个数(x,y)（其中1≤x,y≤n），打字机会显示第x个打印的字符串在第y个打印的字符串中出现了多少次。
阿狸发现了这个功能以后很兴奋，他想写个程序完成同样的功能，你能帮助他么？

Input

输入的第一行包含一个字符串，按阿狸的输入顺序给出所有阿狸输入的字符。
第二行包含一个整数m，表示询问个数。
接下来m行描述所有由小键盘输入的询问。其中第i行包含两个整数x, y，表示第i个询问为(x, y)。
1<=N<=10^5
1<=M<=10^5
输入总长<=10^5

Output

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

Sample Input

aPaPBbP
3
1 2
1 3
2 3

Sample Output

2
1
0

HINT

 

Source

题解：

好题。

一个讲得很详细的题解：http://blog.csdn.net/huzecong/article/details/7769988

思路：这题的想法有点神啊....

先构建AC自动机，然后怎么判断一个串b是a的子串呢？用fail指针就可以了。如果a串中有节点可以通过fail指针走到b的终止节点，那么b就在a中出现过。有n个节点可以走到b，那么b就出现过n次。

现在就有一个暴力的想法，枚举a串的每个节点的fail看是否能到b，但是这是显然会T的。

然后我们可以倒过来想，把fail指针反向，建一棵fail树，对于b串，统计子树中有多少个a串的节点即可。

子树的节点的dfs序是相连的。

这样我们就可以用树状数组维护一下就好了。

#include<iostream>
#include<cstring>
#include<cstdio>
#define maxn 100005
using namespace std;
char s[maxn];
int son[maxn][26],fail[maxn],sum[maxn],lis[maxn];
int pre[maxn],now[maxn],v[maxn],fa[maxn];
int ppre[maxn],nnow[maxn],vv[maxn],t[maxn];
int ans[maxn],l[maxn],r[maxn];
int n,tot,cnt,id,len,T;
void add(int x,int val)
{
    for(int i=x;i<=T;i+=i&(-i))t[i]+=val;  
}
int query(int x)
{
    int sum=0;
    for(int i=x;i;i-=i&-i)sum+=t[i];
    return sum;
}
void build()
{
    scanf("%s",s+1);  len=strlen(s+1);
    int p=0; tot=0; id=0; tot=0;
    for (int i=1; i<=len; i++)
    {
        if (s[i]=='P') sum[++id]=p;
        else
        if (s[i]=='B') p=fa[p];
        else
        {
            int v=son[p][s[i]-'a'];
            if (!v) son[p][s[i]-'a']=++tot,fa[tot]=p;
            p=son[p][s[i]-'a'];
        }
    }
    //cout<<id<<endl;
}
void failed()
{
    int head=0,tail=1; lis[1]=0; fail[0]=-1;
    while (head<tail)
    {
        int x=lis[++head];
        for (int i=0; i<26; i++)
        {
            int v=son[x][i];
            if (!v) continue;
            int p=fail[x];
            while (p!=-1 && !son[p][i]) p=fail[p];
            if (p==-1) fail[v]=0;
            else
            fail[v]=son[p][i];
            lis[++tail]=v;
        }
    }
     
    for (int i=1; i<=tot; i++)
    {
        ppre[i]=nnow[fail[i]];  nnow[fail[i]]=i; vv[i]=i;
        //cout<<fail[i]<<" "<<i<<endl;
    }
}
void insert()
{
    cin>>n;
    for (int i=1; i<=n; i++)
    {
        int x,y;
        cin>>x>>y;
        pre[i]=now[y]; now[y]=i; v[i]=x;
    }
}
void dfs(int x)
{
    l[x]=++T;
    for (int i=nnow[x]; i; i=ppre[i])
    {
        dfs(vv[i]);
    }
    r[x]=T;
}
void work()
{
    int kk=0;
    add(l[0],1); 
    int id=0;
    for (int i=1; i<=len; i++)
    {
        if (s[i]=='P') 
        {
            ++id;
            for (int p=now[id]; p; p=pre[p])
            {
                 
                int t=sum[v[p]];
                ans[p]=query(r[t])-query(l[t]-1); 
            }
        }
        else
        if (s[i]=='B') add(l[kk],-1),kk=fa[kk];
        else
        {
            kk=son[kk][s[i]-'a'];add(l[kk],1);  
        } 
    }
}
void print()
{
    for (int i=1; i<=n; i++)
    printf("%d
",ans[i]);
}
int main()
{
    build();
    failed();
    insert();
    dfs(0);
    work();
    print();
}