P2414 [NOI2011] 阿狸的打字机

2018-04-13 21:42:55


求解多模式串的kmp问题,显然是AC自动机了

那么接下来考虑如何将复杂的问题转化

在insert字符串时,记录下每个节点的父亲

如果遇到'B'操作(删除打印序列中的最后一位),就跳回父亲

如果遇到'P'操作,就记录下这个打印序列

tail数组表示第i个打印序列的最后一位

ed数组表示i节点是哪一个打印序列的最后一位

遇到小写字母时直接插入就好了

但要注意用son数组将ch数组复制

因为getfail会改变ch数组,但后面仍需使用之前的值

随后可以发现AC自动机的一个神奇性质:

如果节点A的fail指针指向B,则B对应的字符串一定在A中出现

有了这一性质,就可以将问题转化为:

在fail树中,以X结束点为根的子树中,有多少个点属于Y

考虑离线操作

把询问按照y从小到大排序

用邻接表重新构建fail树

然后找到每一个y值对应的区间(就是哪几个询问的y值相同)

dfs整棵fail树,找出dfs序和各个子树大小

这样一来,只要钉死“属于Y的节点”这个条件就可以序列统计了

所以dfs整棵trie树,让每一个节点对应的序列点+1(回溯时再-1)

如果这个节点是一个打印序列的结尾,那么就找出关于这个节点的询问区间求和

显然可以用树状数组了(然而还是要抄题解)

用结构体封装一下还是比较清晰的

#include<cstdio>
#include<cstring>
#include<cctype>
#include<queue>
#include<algorithm>
#define reg register
#define reset(a) memset((a),0,sizeof(a))
using namespace std;
const int N=1e5+5;
char p[N];
struct edge
{
    int to,nxt;
}edge[N<<1];
struct question
{
    int x,y,id,ans;
}g[N];
int n,num,head[N],idx[N],tot[N],l[N],r[N];
struct Aho_Corasick_automation
{
    int ch[N][26],son[N][26],tail[N],ed[N],fail[N],f[N],cnt,val[N];
    inline void clear()
    {
        reset(ch); reset(son);
        reset(fail); reset(f);
        reset(val); cnt=0;
    }
    inline void insert(char *s)
    {
        int u=0,len=strlen(s);
        for (reg int i=0;i<len;i++)
        {
            if (s[i]=='B') u=f[u];
            else if (s[i]=='P')
            {
                tail[++n]=u; ed[u]=n;
            }
            else
            {
                int v=s[i]-'a';
                if (!ch[u][v])
                {
                    son[u][v]=ch[u][v]=++cnt;
                    f[ch[u][v]]=u;
                }
                u=ch[u][v];
            }
        }
    }
    inline void getfail()
    {
        queue<int>q;
        for (reg int i=0;i<26;i++)
        {
            int v=ch[0][i];
            if (v) q.push(v);
        }
        while (!q.empty())
        {
            int u=q.front(); q.pop();
            for (reg int i=0;i<26;i++)
            {
                int v=ch[u][i];
                if (v) q.push(v),fail[v]=ch[fail[u]][i];
                else ch[u][i]=ch[fail[u]][i];
            }
        }
    }
}AC;
struct Treearray
{
    int c[N<<1];
    inline int lowbit(int x){return x&(-x);}
    inline void add(int x,int p)
    {
        while (x<=num)
        {
            c[x]+=p; x+=lowbit(x);
        }
    }
    inline int sum(int x)
    {
        int res=0;
        while (x)
        {
            res+=c[x]; x-=lowbit(x);
        }
        return res;
    }
}T;
inline int read()
{
    int x=0,w=1;
    char c=getchar();
    while (!isdigit(c)&&c!='-') c=getchar();
    if (c=='-') c=getchar(),w=-1;
    while (isdigit(c))
    {
        x=(x<<1)+(x<<3)+c-'0';
        c=getchar();
    }
    return x*w;
}
inline void add_edge(int from,int to)
{
    edge[++num].nxt=head[from];
    edge[num].to=to;
    head[from]=num;
}
bool cmp(question a,question b)
{
    return a.y<b.y;
}
bool cmp2(question a,question b)
{
    return a.id<b.id;
}
void dfs1(int k)
{
    idx[k]=++num; tot[k]=1;
    for (reg int i=head[k];i;i=edge[i].nxt)
    {
        int v=edge[i].to;
        if (!idx[v])
        {
            dfs1(v); tot[k]+=tot[v];
        }
    }
}
void dfs2(int k)
{
    T.add(idx[k],1);
    if (AC.ed[k])
      for (reg int i=l[AC.ed[k]];i<=r[AC.ed[k]];i++)
      {
          int now=AC.tail[g[i].x];
          g[i].ans=T.sum(idx[now]+tot[now]-1)-T.sum(idx[now]-1);
      }
    for (reg int i=0;i<26;i++)
      if (AC.son[k][i]) dfs2(AC.son[k][i]);
    T.add(idx[k],-1);
}
int main()
{
    scanf("%s",p); AC.clear();
    AC.insert(p); AC.getfail();
    int m=read();
    for (reg int i=1;i<=m;i++)
      g[i].x=read(),g[i].y=read(),g[i].id=i;
    sort(g+1,g+m+1,cmp);
    for (reg int i=1;i<=AC.cnt;i++)
    {
        add_edge(AC.fail[i],i);
        add_edge(i,AC.fail[i]);
    }
    int now=1;
    for (reg int i=1;i<=m;i=now)
    {
        l[g[i].y]=i;
        while (g[now].y==g[i].y) ++now;
        r[g[i].y]=now-1;
    }
    num=0; dfs1(0); dfs2(0);
    sort(g+1,g+m+1,cmp2);
    for (reg int i=1;i<=m;i++)
      printf("%d\n",g[i].ans);
    return 0;
}