about 4 years ago

好恶心……

调了好久最后发现是pos打成i……

将ac自动机上的fail边反向变成一个fail树。同样的,也将查询反向建一棵树

将查询中后边的字符串的每个结点打标记。然后再dfs序上维护树状数组。

总的来说是一个非常神的做法

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cstdlib>

#include<queue>

#define maxn 100001

#define size 27

#define maxm

using namespace std;
char st[maxn];
struct wide
{
    int next[maxn],point[maxn],v[maxn],widen;
    wide(){widen=-1;
    memset(next,-1,sizeof(next));memset(point,-1,sizeof(point));}
    void addedge(int x,int y)
    {
        widen++;next[widen]=point[x];point[x]=widen;v[widen]=y;
    }
} fail,query;
int n,tot=0,cnt=0,stn=0;
int ch[maxn][size]={0};
int f[maxn]={0},fa[maxn]={0},dy[maxn]={0},end[maxn]={0};
int val[maxn]={0};
int a[maxn]={0},ans[maxn]={0};
int head[maxn]={0},til[maxn]={0};
int readln()
{
    char c=getchar();int result=0,bj=1;
    while (c!='-'&&!(c<='9'&&c>='0')) c=getchar();
    if (c=='-') bj=-1,c=getchar();
    while (c<='9'&&c>='0') result=result*10+c-'0',c=getchar();
    return result*bj;
}
void build()
{
    int i,l=strlen(st),pos=0;
    for (i=0;i<l;i++)
    {
        if (st[i]=='B') {pos=fa[pos];continue;}
        if (st[i]=='P') {val[pos]=++stn;end[stn]=pos;continue;}
        if (!ch[pos][st[i]-'a'+1]){ch[pos][st[i]-'a'+1]=++tot;}
        fa[ch[pos][st[i]-'a'+1]]=pos;
        pos=ch[pos][st[i]-'a'+1]; dy[i]=pos;
    }
}
queue<int>q;
void prepare()
{
    int i,j,k,pos=0;
    for (i=0;i<size;i++)
    {
        if (ch[pos][i]) {q.push(ch[pos][i]);fail.addedge(0,ch[pos][i]);}
    }
    while (!q.empty())
    {
        j=q.front();q.pop();
        for (i=1;i<size;i++)
        {
            if (!ch[j][i]) {ch[j][i]=ch[f[j]][i];continue;}
            q.push(ch[j][i]);
            pos=f[j];
            while (pos&&!ch[pos][i]) pos=f[pos];
            f[ch[j][i]]=ch[pos][i];
            fail.addedge(f[ch[j][i]],ch[j][i]);
        }
    }
}
void dfs(int now)
{
    head[now]=++cnt;
    for (int k=fail.point[now];k!=-1;k=fail.next[k])
    if (!head[fail.v[k]]) dfs(fail.v[k]);
    til[now]=cnt;
}
int lowbit(int x)
{
    return x&(-x);
}
void change(int pos,int delta)
{
    for (int i=pos;i<=cnt;i+=lowbit(i))a[i]+=delta;
}
int querysum(int pos)
{
    int result=0,i;
    for (i=pos;i>0;i-=lowbit(i)) result+=a[i];
    return result;
}
int main()
{
    int i,j,k,x,y,l,pos=0;
    scanf("%s",st);l=strlen(st);
    n=readln();
    for (i=1;i<=n;i++) {x=readln();y=readln();query.addedge(y,x);}
    build();
    prepare();
    dfs(0);
    for (i=0;i<l;i++)
    {
        if (st[i]=='B') {change(head[pos],-1);pos=fa[pos];continue;}
        if (st[i]=='P')
          for (j=query.point[val[pos]];j!=-1;j=query.next[j])
            ans[j]=querysum(til[end[query.v[j]]])-querysum(head[end[query.v[j]]]-1);
        else
          {
            pos=ch[pos][st[i]-'a'+1];
            change(head[pos],1);
          }
    }
    for (i=0;i<=query.widen;i++) printf("%d\n",ans[i]);
}
← 【bzoj1005】【HAOI2008】【prufer编码】【排列组合】明明的烦恼 【poj1061】【数论】【扩展欧几里德+逆元】青蛙的约会 →
 
comments powered by Disqus