【BZOJ】【P 2444】【Noi 2011】【タヌキのタイプライター】【題解】【failツリー+dfsシーケンス+ツリー配列】
2531 ワード
転送ゲート:http://www.lydsy.com/JudgeOnline/problem.php?id=2434
問題の解がたくさんあるのでやめます。
コード:
問題の解がたくさんあるのでやめます。
コード:
#include<bits/stdc++.h>
#define idx(c) (c-'a')
#define lowbit(x) (x&-x)
using namespace std;
const int maxn=1e5+5;
typedef pair<int,int> pi;
vector<int>d,lef,rig;
vector<pi>Q[maxn];
char s[maxn];
int n,m,len,anss[maxn],tot,mp[maxn],vmp[maxn];
struct node{
int val,id;
node *go[26],*fail,*last,*pre;
vector<node*>son;
node(node *C=0){
for(int i=0;i<26;i++)go[i]=C;
fail=last=C;pre=C;id=0;val=0;
}
}*Null,*root;
int cnt=0;
node *newnode(){
node *x=new node(Null);
x->id=++cnt;return x;
}
void build(){
Null=newnode();Null->fail=Null->last=Null;
for(int i=0;i<26;i++)Null->go[i]=Null;
root=Null;
node *u=root;
for(int i=0;i<len;i++){
if(s[i]=='B'){u=u->pre;continue;}
if(s[i]=='P'){++n;mp[n]=u->val?mp[u->val]:n;u->val=u->val?u->val:n;vmp[u->val]=u->id;continue;}
int v=idx(s[i]);
if(u->go[v]==Null)u->go[v]=newnode();
u->go[v]->pre=u;u=u->go[v];
}
}
void get_fail(){
queue<node*>q;
for(int i=0;i<26;i++)if(root->go[i]!=Null)
q.push(root->go[i]),root->son.push_back(root->go[i]);
while(!q.empty()){
node *u=q.front(),*v;q.pop();
for(int i=0;i<26;i++)if((v=u->go[i])!=Null){
q.push(v);node *j=u->fail;
while(j!=Null&&j->go[i]==Null)j=j->fail;
v->fail=j->go[i];j->go[i]->son.push_back(v);
v->last=v->fail->val?v->fail:v->last;
}
}
}
int get(int x){
int ans=0;
while(x)ans+=d[x],x-=lowbit(x);
return ans;
}
void updata(int x,int f){
while(x<d.size())d[x]+=f,x+=lowbit(x);
}
void _dfs(node *u){
lef[u->id]=++tot;
for(int i=0;i<u->son.size();i++)
_dfs(u->son[i]);
rig[u->id]=tot;
}
void dfs(node *u){
updata(lef[u->id],1);
for(int i=0;i<Q[u->val].size();i++)
anss[Q[u->val][i].second]=get(rig[vmp[Q[u->val][i].first]])-get(lef[vmp[Q[u->val][i].first]]-1);
for(int i=0;i<26;i++)if(u->go[i]!=Null)
dfs(u->go[i]);
updata(lef[u->id],-1);
}
int main(){
scanf("%s",s);len=strlen(s);
build();get_fail();
d.resize(cnt+1);
lef.resize(cnt+1);
rig.resize(cnt+1);
_dfs(root);
scanf("%d",&m);
for(int i=1;i<=m;i++){
int x,y;scanf("%d%d",&x,&y);
Q[mp[y]].push_back(make_pair(mp[x],i));
}dfs(root);
for(int i=1;i<=m;i++)printf("%d
",anss[i]);
return 0;
}