# P2414 [NOI2011] Ali's typewriter (build a fail tree on AC automata to find the dfs order, and query it with a tree array on the tire diagram)

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],fail[maxn],fa[maxn],num,ed[maxn],vis[maxn];
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
{
int to,nxt,id;
void get_fail()
{
memcpy(vis,zi,sizeof vis );
queue<int>q;
for(int i=0;i<=25;i++)
if( vis[i] )	q.push( vis[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)
{
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] );
}
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);