[NOI2011]阿狸的打字机

首先，可以发现这样一个性质
x在y中出现过=======y的某个前缀的后缀等于x。

先把AC自动机建出来后。
y的每一个前缀就是它在trie树上所遍历到的每一个点。
check这个点的后缀是否等于x也就是看沿着fail指针向上能否走到x。
这也就等价于这个点在x的子树中。
考虑去如何加速这个过程。
可以先把属于y的每一个点都先标记一下，对于询问x直接查询子树权值和即可。
综上，把询问按照y排序，在trie树上游走，进入一个点就给这个点+1，退出这个点就给这个点-1。
当走完y以后，处理所有关于y的询问。

#include<iostream>
#include<cctype>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<queue>
#include<cstdlib>
#include<algorithm>
#define N 1100000
#define eps 1e-7
#define inf 1e9+7
#define ll long long
using namespace std;
inline int read()
{
    char ch=0;
    int x=0,flag=1;
    while(!isdigit(ch)){ch=getchar();if(ch==‘-‘)flag=-1;}
    while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-‘0‘;ch=getchar();}
    return x*flag;
}
queue<int>q;
char ch[N];
int root=1,size=1,s[N],f[N],id[N],nxt[N][27];
struct edge
{
    int to;
    int nxt;
}e[N];
int num,head[N];
inline void add(int x,int y)
{
    e[++num]=(edge){y,head[x]};
    head[x]=num;
}
struct node
{
    int x,y,id;
}p[N];
bool cmp(node a,node b)
{
    return a.y<b.y;
}
int m,times,sz[N],dfn[N],ans[N];
void dfs(int x)
{
    sz[x]=1;dfn[x]=++times;
    for(int i=head[x];i;i=e[i].nxt)
    {
        int to=e[i].to;
        dfs(to);sz[x]+=sz[to];
    }
}
struct Fenwick_Tree
{
    int s[N];
    inline void add(int x,int num)
    {
        for(;x<=size;x+=((x)&(-x)))s[x]+=num;
    }
    inline int query(int x)
    {
        int ans=0;
        for(;x;x-=((x)&(-x)))ans+=s[x];
        return ans;
    }
}T;
void insert()
{
    int n=strlen(ch),x=root,top=0,cnt=0;
    s[0]=root;
    for(int i=0;i<n;i++)
    {
        if(‘a‘<=ch[i]&&ch[i]<=‘z‘)
        {
            int k=ch[i]-‘a‘;
            if(!nxt[x][k])nxt[x][k]=++size;
            x=nxt[x][k];s[++top]=x;
        }
        if(ch[i]==‘B‘)
        {
            top--;
            x=s[top];
        }
        if(ch[i]==‘P‘)
        {
            cnt++;
            id[cnt]=x;
        }
    }   
}
void build()
{
    q.push(root);
    while(!q.empty())
    {
        int x=q.front();
        q.pop();
        for(int i=0;i<26;i++)
        {
            if(nxt[x][i])
            {
                if(x!=root)f[nxt[x][i]]=nxt[f[x]][i];
                else f[nxt[x][i]]=root;
                q.push(nxt[x][i]);
            }
            else
            {
                if(x!=root)nxt[x][i]=nxt[f[x]][i];
                else nxt[x][i]=root;
            }
        }
    }
}
void solve()
{
    int n=strlen(ch),x=root,top=0,cnt=0;
    s[0]=root;
    for(int i=0,j=0;i<n;i++)
    {
        if(‘a‘<=ch[i]&&ch[i]<=‘z‘)
        {
            int k=ch[i]-‘a‘;
            x=nxt[x][k];s[++top]=x;
            T.add(dfn[s[top]],+1);
        }
        if(ch[i]==‘B‘)
        {
            T.add(dfn[s[top]],-1);
            top--;x=s[top];
        }
        if(ch[i]==‘P‘)
        {
            cnt++;
            while(j<m&&cnt==p[j+1].y)
            {
                int k=id[p[++j].x];
                ans[p[j].id]=T.query(dfn[k]+sz[k]-1)-T.query(dfn[k]-1);
            }
        }
    }   
}
int main()
{
    scanf("%s",ch);insert();build();
    for(int i=2;i<=size;i++)add(f[i],i);
    dfs(root);
    m=read();
    for(int i=1;i<=m;i++)
    {
        p[i].id=i;
        p[i].x=read();
        p[i].y=read();
    }
    sort(p+1,p+m+1,cmp);
    solve();
    for(int i=1;i<=m;i++)printf("%d\n",ans[i]); 
    return 0;
}

[NOI2011]阿狸的打字机

原文：https://www.cnblogs.com/Creed-qwq/p/10074396.html