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] ); }