Luogu2414 [NOI2011]阿狸的打字机

先建AC自动机，然后建next树，然后把每个询问加进AC自动机上，dfs一遍，把当前insta的节点加进树状数组，如果碰到询问就在树状数组上查询区间和，回溯时再把节点从树状数组中删去

#include<bits/stdc++.h>
#define maxn 100005
using namespace std;

struct node{
    int lc[26],next,pre;
    vector<int> query;
}AC[maxn],trie[maxn];

char s[maxn];
int c[maxn];
int m,len,tot,match[maxn],siz[maxn],n;
int edge[maxn],head[maxn],nextt[maxn];
int a[maxn],b[maxn],ans[maxn],num[maxn];
queue<int> q;

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

int ask(int x){
    int sum=0;
    for(;x;x-=(x&-x)) sum+=c[x];
    return sum;
}

void add(int x,int y,int tot){
    edge[tot]=y;nextt[tot]=head[x];head[x]=tot;
}

void build_trie(){
    int root=0;
    for(int i=1;i<=len;i++){
        if('a'<=s[i]&&s[i]<='z'){
            if(!AC[root].lc[s[i]-'a']) AC[root].lc[s[i]-'a']=++tot,AC[AC[root].lc[s[i]-'a']].pre=root;
            root=AC[root].lc[s[i]-'a'];
        }
        if(s[i]=='B') root=AC[root].pre;
        if(s[i]=='P') match[++n]=root;
    }
}

void build_AC(){
    for(int i=0;i<26;i++) if(AC[0].lc[i]) q.push(AC[0].lc[i]);
    while(!q.empty()){
        int x=q.front();
        q.pop();
        for(int i=0;i<26;i++){
            if(AC[x].lc[i]) AC[AC[x].lc[i]].next=AC[AC[x].next].lc[i],q.push(AC[x].lc[i]);
            else AC[x].lc[i]=AC[AC[x].next].lc[i];
        }
    }
}

void dfs(int x){
    if(x) aadd(num[x],1);
    for(int i=0;i<AC[x].query.size();i++){
        int t=AC[x].query[i];
        ans[t]=ask(num[match[a[t]]]+siz[match[a[t]]]-1)-ask(num[match[a[t]]]-1);
    }
    for(int i=0;i<26;i++)
        if(trie[x].lc[i])
            dfs(trie[x].lc[i]);
    if(x) aadd(num[x],-1);
}

void dfs1(int x){
    siz[x]=1;
    num[x]=++tot;
    for(int i=head[x];i;i=nextt[i]){
        int y=edge[i];
        dfs1(y);
        siz[x]+=siz[y];
    }
}

int main(){
    scanf("%s",s+1);
    len=strlen(s+1);
    build_trie();
    for(int i=0;i<=tot;i++) trie[i]=AC[i];
    build_AC();
    for(int i=1;i<=tot;i++) add(AC[i].next,i,i);
    tot=0;
    dfs1(0);
    scanf("%d",&m);
    for(int i=1;i<=m;i++){
        scanf("%d%d",&a[i],&b[i]);
        AC[match[b[i]]].query.push_back(i);
    }
    dfs(0);
    for(int i=1;i<=m;i++) printf("%d\n",ans[i]);
    return 0;
}

Luogu2414 [NOI2011]阿狸的打字机

原文：https://www.cnblogs.com/ElevenX/p/11609415.html