记录编号	379628	评测结果	AAAAAAAAAA
题目名称	[NOI 2011]阿狸的打字机	最终得分	100
用户昵称	yourfather	是否通过	通过
代码语言	C++	运行时间	0.395 s
提交时间	2017-03-07 06:37:04	内存使用	18.43 MiB

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
const int maxn = 100010;
vector<int> v[maxn];
int ch[maxn][26]={0},fail[maxn]={0},dan[maxn]={0};
int q[maxn]={0},front = -1,back = 0;
int match[maxn]={0};
struct TEXT{
	int x,y,id,ans ;
	bool operator < (const TEXT &a)const{return y < a.y;}
}t[100010];
int N,M,y[maxn]={0},node = 0,st[maxn]={0},ed[maxn]={0};
struct Link{int to,next;}link[maxn]={0};
int head[maxn]={0},tot = 0,fa[maxn]={0};
void add(int from,int to){
	link[++tot].to = to;
	link[tot].next = head[from];
	head[from] = tot;
}
char str[1000100];
void Insert(){
	int n = strlen(str),now = 0,cnt = 0;
	for(int i = 0;i < n;i++){
		if(str[i] >='a' && str[i] <= 'z'){
			if(!ch[now][str[i]-'a'])ch[now][str[i]-'a'] = ++node;
			fa[ch[now][str[i]-'a']] = now;
			now = ch[now][str[i]-'a'];
		}
		if(str[i] == 'B')now = fa[now];
		if(str[i] == 'P'){
			cnt++;
			match[cnt] = now;
			v[now].push_back(cnt);
		}
	}
}
void getfail(){
	for(int i = 0;i < 26;i++)
		if(ch[0][i])q[++front] = ch[0][i];
	while(back <= front){
		int now = q[back++];
		for(int i = 0;i < 26;i++){
			int &u = ch[now][i];
			if(!u)continue;
			q[++front] = u;
			int temp = fail[now];
			while(temp && !ch[temp][i])temp =fail[temp];
			temp = ch[temp][i];
			fail[u] = temp;
		}
	}
}
int cnt = 0,C[maxn]={0};
inline int lowbit(int x){return x&-x;}
inline void Updata(int x,int y){for(;x<=cnt;x += lowbit(x))C[x]+=y;}
inline int get(int x){
	int ret = 0;
	for(;x;x-=lowbit(x))ret += C[x];
	return ret;
}
void DFS(int x){
	st[x] = ++cnt;
	for(int i = head[x];i;i=link[i].next){
		DFS(link[i].to);
	}
	ed[x] = cnt;
}
void Build(){tot = 0;
	for(int i = 1;i <= node;i++)if(fail[i]!=i)add(fail[i],i);
	DFS(0);
}
void find(int x){
	for(int i = 0;i < v[x].size();i++){
		int loc = lower_bound(y+1,y+1+N,v[x][i])-y;
		if(y[loc]!=v[x][i])continue;
		while(y[loc] == v[x][i]){
			int n = match[t[loc].x];
			t[loc].ans = get(ed[n])-get(st[n]-1);
			loc++;
		}
	}
	for(int i = 0;i < 26;i++){
		if(!ch[x][i])continue;
		Updata(st[ch[x][i]],1);
		find(ch[x][i]);
		Updata(st[ch[x][i]],-1);
	}
}
bool comp(const TEXT &a,const TEXT &b){return a.id < b.id;}
int main(){
	freopen("noi2011_type.in","r",stdin);
	freopen("noi2011_type.out","w",stdout);
	scanf("%s",str);
	Insert();
	scanf("%d",&N);
	for(int i = 1;i <= N;i++)scanf("%d%d",&t[i].x,&t[i].y),t[i].id = i;
	sort(t+1,t+1+N);
	for(int i = 1;i <= N;i++)y[i] = t[i].y;
	getfail();Build();
	find(0);
	sort(t+1,t+1+N,comp);
	for(int i = 1;i <= N;i++)printf("%d\n",t[i].ans);
	return 0;
}