비버 타자기

전송 문:http://www.lydsy.com:808/JudgeOnline/problem.php?id=2434
아주 상세 하 게 말 한 문제 풀이http://blog.csdn.net/huzecong/article/details/7769988
사고방식:이 문제 의 생각 은 좀 신기 하 다.
먼저 AC 자동 동 기 를 구축 한 다음 에 b 가 a 의 하위 꼬치 라 고 어떻게 판단 합 니까?페 일 포인터 로 하면 돼 요.만약 에 a 열 에 노드 가 fail 지침 을 통 해 b 의 종료 노드 로 갈 수 있다 면 b 는 a 에 나타 난 적 이 있 습 니 다.n 개의 노드 가 b 까지 갈 수 있 으 면 b 는 n 번 나 온 적 이 있다.
지금 은 폭력 적 인 생각 이 있 습 니 다.a 꼬치 의 모든 노드 의 fail 을 들 어 b 가 도착 할 수 있 는 지 없 는 지 를 보 겠 습 니 다.그러나 이것 은 분명히 T 가 될 것 입 니 다.
그 다음 에 우 리 는 fail 지침 을 반대로 해서 fail 나 무 를 만 들 고 b 꼬치 에 대해 서브 트 리 에 a 꼬치 의 노드 가 몇 개 있 는 지 통계 하면 된다.
하위 트 리 의 노드 dfs 순서 가 연결 되 어 있 습 니 다.
이렇게 하면 우 리 는 나무 모양 의 배열 로 지 킬 수 있 었 으 면 좋 겠 다.

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
const int maxn=100010;
using namespace std;
int m,len,num,preq[maxn],nowq[maxn],sonq[maxn],l[maxn],r[maxn],bit[maxn],pos[maxn],cnt,pre[maxn],now[maxn],son[maxn],ans[maxn];char s[maxn],ch;
void change(int x,int val){for (;x<=cnt;x+=x&-x) bit[x]+=val;}
int query(int x){
	int res=0;
	for (;x;x-=x&-x) res+=bit[x];
	return res;
}
void add(int a,int b){pre[++num]=now[a],now[a]=num,son[num]=b;}
void read(int &x){
	for (ch=getchar();!isdigit(ch);ch=getchar());
	for (x=0;isdigit(ch);ch=getchar()) x=x*10+ch-'0';
}

struct AC_DFA{
	int tot,ch[maxn][26],fail[maxn],q[maxn],fa[maxn],head,tail;
	void build(){
		int p=0,id=0;
		for (int i=0;i<len;i++)
			if (s[i]=='P') pos[++id]=p;
			else if (s[i]=='B') p=fa[p];
			else{
				if (!ch[p][s[i]-'a']) ch[p][s[i]-'a']=++tot,fa[tot]=p;
				p=ch[p][s[i]-'a'];
			}
	}
	void getfail(){
		head=0,q[tail=1]=0,fail[0]=-1;
		while (head!=tail){
			int x=q[++head];
			for (int i=0;i<26;i++)
				if (ch[x][i])
					q[++tail]=ch[x][i],fail[ch[x][i]]=x==0?0:ch[fail[x]][i];
				else ch[x][i]=x==0?0:ch[fail[x]][i];
		}
	}
	void dfs(int x){
		l[x]=++cnt;
		for (int y=now[x];y;y=pre[y])
			dfs(son[y]);
		r[x]=cnt;
	}
	void work(){
		int p=0,id=0;
		change(l[0],1);
		for (int i=0;i<len;i++)
			if (s[i]=='P'){
				id++;
				for (int y=nowq[id];y;y=preq[y]){
					int t=pos[sonq[y]];
					ans[y]=query(r[t])-query(l[t]-1);
				}
			}
			else if (s[i]=='B') change(l[p],-1),p=fa[p];
			else p=ch[p][s[i]-'a'],change(l[p],1);
	}
}T;

int main(){
	scanf("%s%d",s,&m);len=strlen(s);
	for (int i=1,x,y;i<=m;i++){
		read(x),read(y);
		preq[i]=nowq[y],sonq[i]=x,nowq[y]=i;
	}
	T.build(),T.getfail();
	for (int i=1;i<=T.tot;i++) add(T.fail[i],i);
	T.dfs(0),T.work();
	for (int i=1;i<=m;i++) printf("%d
",ans[i]);
	return 0;
}