LINK

m m m times of inquiry, the first time of each inquiry x x The string of times x is in the y y How many times does it appear in the string of y times

For example, the sample aPaPBbP

The three strings are a, AA and ab

Consider establishing a for these strings A C AC AC automata

For a query ( x , y ) (x,y) (x,y)

We just need to find the automata x x x corresponding node a a a and y y Node corresponding to y b b b

We need to find the root node to a a Substring of a from root node to y y How many times does it appear in the substring of y

T 1 \color{Red}{T1} T1

This question is equivalent to, b b How many prefixes does the b string have a a a string

We know the of automata f a i l fail fail is the longest suffix, so we can enumerate prefixes and jump violently f a i l fail fail judgment

Then we might as well record the father of each node, and then start from the node b b b start

Keep jumping violently f a i l fail fail until you jump to the node x x x. Add one to the answer

Then from the node b b b's father began to jump violently f a i l . . . . . . fail...... fail......

So, 40 points Code LINK

T 2 \color{Red}{T2} T2

Violent jump f a i l fail The complexity of fail is too high to accept

Consider establishing f a i l fail fail tree, f a i l fail If the fail side is reversed, the problem becomes

t i r e tire Tie tree root node to y y How many nodes on the path of y belong to f a i l fail fail tree x x Subtree node of x

Notice that we have two graphs here. One is t i r e tire tire diagram, one is f a i l fail fail tree

We find out f a i l fail fail tree d f s dfs dfs order, recorded as d f n [ u ] dfn[u] dfn[u]

Then go d f s     t i r e dfs\ \ \ tire dfs tire diagram, every point u u u just put d f n [ u ] dfn[u] dfn[u] equals on tree array 1 1 1

Then after traversing this point, let d f n [ u ] dfn[u] dfn[u] equals on tree array 0 0 0

In this way, when we traverse to the node u u u, the root node to u u The point on the u path must be on the tree array 1 1 1

Other points must be 0 0 0, we can deal with it now u u u all inquiries about

The form of these inquiries is t i r e tire Tie tree root node to u u How many nodes on the path of u belong to f a i l fail fail tree v v Subtree node of v

We didn't find out just now f a i l fail fail tree d f s dfs dfs sequence? Subtree d f s dfs dfs order must be continuous, so you can query it directly

Be careful

We're building f a i l fail The fail pointer will change when t i r e tire tire diagram, so an additional copy is required t i r e tire Tier array

#include <bits/stdc++.h>
using namespace std;
const int maxn = 4e5+10;
char a[maxn],b[maxn];
int top,id[maxn],zi[maxn][26],fail[maxn],fa[maxn],num,ed[maxn],vis[maxn][26];
int m,ans[maxn];
//Tree array 
struct tree_array
{
	int sum[maxn],n;
	int lowbit(int x){ return x&(-x); }
	void add(int x,int val){ for(;x<=n;x+=lowbit(x) ) sum[x]+=val;}
	int ask(int x){int ans=0;for(;x;x-=lowbit(x) ) ans+=sum[x];return ans;}
	int query(int l,int r){ return ask(r)-ask(l-1); }
}t;
//inquiry 
struct askedge
{
	int to,nxt,id;
}d[maxn]; int head[maxn],cnt=1;
void add(int u,int v,int id){d[++cnt]=(askedge){v,head[u],id},head[u]=cnt;}
void get_fail()
{
	memcpy(vis,zi,sizeof vis );
	queue<int>q;
	for(int i=0;i<=25;i++)
		if( vis[0][i] )	q.push( vis[0][i] );
	while( !q.empty() )
	{
		int u = q.front(); q.pop();
		for(int i=0;i<=25;i++)
		{
			if( vis[u][i] )	fail[vis[u][i]] = vis[fail[u]][i],q.push( vis[u][i] );
			else	vis[u][i] = vis[fail[u]][i];
		}
	}
}
//fail tree
vector<int>vec[maxn]; 
void get_failtree()
{
	for(int i=1;i<=num;i++)
		vec[ fail[i] ].push_back(i);		
}
int dfu,dfn[maxn],siz[maxn];
void dfs_failtree(int u)
{
	dfn[u] = ++dfu; siz[u] = 1;
	for( auto v:vec[u] )
	{
		if( dfn[v] )	continue;
		dfs_failtree(v); siz[u] += siz[v];
	}
}
void dfs_tire(int u)
{
	t.add( dfn[u],1 );
	if( ed[u]!=0 )
	{
		for(int i=head[u];i;i=d[i].nxt )//Handle all queries 
		{
			int v = d[i].to;
			ans[d[i].id] = t.query( dfn[v],dfn[v]+siz[v]-1 );
		}
	}
	for(int i=0;i<=25;i++)
		if( zi[u][i] )	dfs_tire( zi[u][i] );
	t.add( dfn[u],-1 );
}
int main()
{
	cin >> ( a+1 ); int len = strlen( a+1 );
	int now = 0;
	for(int i=1;i<=len;i++)
	{
		if( a[i]>='a'&&a[i]<='z' )
		{
			if( zi[now][a[i]-'a']==0 )
				zi[now][a[i]-'a'] = ++num,fa[num] = now;
			now = zi[now][a[i]-'a'];
		}
		else if( a[i]=='B' )	now = fa[now];
		else if( a[i]=='P' )	id[++top] = now, ed[now] = top;
	}
	cin >> m;
	for(int i=1;i<=m;i++)//Offline inquiry
	{
		int x,y; scanf("%d%d",&x,&y);
		add(id[y],id[x],i);
	} 
	get_fail();
	get_failtree();
	t.n = num+1;
	dfs_failtree(0);
	dfs_tire(0);
	for(int i=1;i<=m;i++)
		printf("%d\n",ans[i] );
}