bzoj 2434 [Noi2011]阿狸的打字机——AC自动机

时间：2021-08-25 21:58:29

题目：https://www.lydsy.com/JudgeOnline/problem.php?id=2434

dfs AC自动机，走过的点权值+1，回溯的时候权值-1；走到询问的 y 串的节点，看一下此时 x 串 fail 树子树和即可。

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

int rdn()

{

  int ret=;bool fx=;char ch=getchar();

  while(ch>''||ch<''){if(ch=='-')fx=;ch=getchar();}

  while(ch>=''&&ch<='')ret=ret*+ch-'',ch=getchar();

  return fx?ret:-ret;

}

const int N=1e5+,K=;

int n,m,tot=,dy[N],c[N][K],tc[N][K],fa[N],fl[N];

int hd[N],xnt,to[N<<],nxt[N<<],dfn[N],ot[N],tim;

int h2[N],t2[N],nt2[N],ans[N];

int q[N],f[N]; char s[N];

void add(int x,int y)

{to[++xnt]=y;nxt[xnt]=hd[x];hd[x]=xnt;fl[y]=x;}

void get_fl()

{

  int he=,tl=;

  for(int i=,v;i<;i++)

    if((v=c[][i]))q[++tl]=v,add(,v),tc[][i]=v;

    else tc[][i]=;

  while(he<tl)

    {

      int k=q[++he],pr=fl[k];

      for(int i=,v;i<;i++)

    if((v=c[k][i]))

      q[++tl]=v,add(tc[pr][i],v),tc[k][i]=v;

    else tc[k][i]=tc[pr][i];

    }

}

void ini_dfs(int cr)

{

  dfn[cr]=++tim;

  for(int i=hd[cr];i;i=nxt[i])

    ini_dfs(to[i]);

  ot[cr]=tim;

}

void Inc(int x,int k){for(;x<=tot;x+=(x&-x))f[x]+=k;}

int qry(int x){int ret=;for(;x;x-=(x&-x))ret+=f[x];return ret;}

void dfs(int cr)

{

  Inc(dfn[cr],);

  for(int i=h2[cr];i;i=nt2[i])

    ans[i]=qry(ot[t2[i]])-qry(dfn[t2[i]]-);

  for(int i=;i<;i++)

    if(c[cr][i])dfs(c[cr][i]);

  Inc(dfn[cr],-);

}

int main()

{

  scanf("%s",s+); n=strlen(s+);

  int cr=,cnt=;

  for(int i=;i<=n;i++)

    {

      if(s[i]>='a')

    {

      c[cr][s[i]-'a']=++tot;

      fa[tot]=cr; cr=tot;

    }

      else if(s[i]=='B')cr=fa[cr];

      else dy[++cnt]=cr;

    }

  get_fl(); ini_dfs();

  m=rdn();

  for(int i=;i<=m;i++)

    {

      int u=rdn(),v=rdn();

      u=dy[u]; v=dy[v];

      t2[i]=u;nt2[i]=h2[v];h2[v]=i;

    }

  dfs();

  for(int i=;i<=m;i++)printf("%d\n",ans[i]);

  return ;

}

相关文章