[NOI2011] 阿狸的打字机

佚名 5年前 (2018-12-25) 算法 1489人围观抢沙发百度已收录

暴力做法：
将字符串建成Trie图。设字符串x的标记节点是idStr[x]，那么对于询问(x,y)，它的答案是从idStr[y]到根的路径上能够通过fail指针条到idStr[x]的节点个数。

优化：
将fail指针反向建立一颗fail树，那么询问(x,y)的答案为统计fail树中isStr[x]的子树内存在多少个在Trie上是idStr[y]的祖先的节点数目。这类字数问题可以使用dfs序+树状数组即可得到解决。

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

请开启-std=c++11选项。

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

const int N=1e5+10;


int cntStr,cntNode;
int fa[N],fail[N],t1[N][26],t2[N][26];
int idStr[N];

int in[N],out[N],cntTime;
vector<int> failTree[N];

int bit[N],ans[N],rootQuery[N];
vector<int> idQuery[N];

void add(int x,int y) {
    for(; x<=cntTime; x+=(x&-x)) bit[x]+=y;
}
int sum(int x,int y=0) {
    for(; x>0; x-=(x&-x)) y+=bit[x];
    return y;
}

void getOrder(int x) {
    in[x]=++cntTime;
    for(int y: failTree[x]) getOrder(y);
    out[x]=cntTime;
}
void getAnswer(int x) {
    add(in[x],1);
    for(int prb: idQuery[x]) {
        ans[prb]=sum(out[rootQuery[prb]])-sum(in[rootQuery[prb]]-1);
    }
    for(int i=0; i<26; ++i) {
        if(t1[x][i]) getAnswer(t1[x][i]);
    }
    add(in[x],-1);
}

void func() {
    static char str[N];
    scanf("%s",str);
    int p=0;
    for(int i=0; str[i]; ++i) {
        if(str[i]=='P') idStr[++cntStr]=p;
        else if(str[i]=='B') p=fa[p];
        else {
            if(!t1[p][str[i]-'a']) {
                t1[p][str[i]-'a']=++cntNode;
                fa[cntNode]=p;
            }
            p=t1[p][str[i]-'a'];
        }
    }
    // puts("builtTrie");
    static queue<int> Q;
    for(int i=0; i<26; ++i) {
        if(t1[0][i]) {
            t2[0][i]=t1[0][i];
            Q.push(t1[0][i]);
        }
    }
    while(!Q.empty()) {
        int x=Q.front();
        Q.pop();
        for(int i=0; i<26; ++i) {
            if(t1[x][i]) {
                fail[t1[x][i]]=t2[fail[x]][i];
                t2[x][i]=t1[x][i];
                Q.push(t1[x][i]);
            } else t2[x][i]=t2[fail[x]][i];
        }
        failTree[fail[x]].push_back(x);
    }
    // puts("buildACAM");
    getOrder(0);
    // puts("buildDFSOrder");
}

int main() {
    func();
    int q,x,y;
    scanf("%d",&q);
    for(int i=1; i<=q; ++i) {
        scanf("%d%d",&x,&y);
        rootQuery[i]=idStr[x];
        idQuery[idStr[y]].push_back(i);
    } 
    getAnswer(0);
    for(int i=1; i<=q; ++i) {
        printf("%d\n",ans[i]);
    }
    return 0;
}

/*
aPaPBbP
3
1 2
1 3
2 3
*/