题目链接：https://acm.hdu.edu.cn/showproblem.php?pid=7084
代码
#include<bits/stdc++.h>
using namespace std;const int N = 3e5 + 10;
int q, len;
char s[N];
int ne[N];
vector<int> g1[N], g2[N];
int dfn1[N], dfn2[N], cnt1, cnt2, rr1[N], rr2[N], re[N], havefa1[N], havefa2[N];
int t[N * 20], sum[N * 20], L[N * 20] , R[N * 20], idx;void getnext()
{
memset(ne, 0, sizeof(ne));int j = 0, k = -1;ne[0] = -1;while(j < len){
if(k == -1 || s[j] == s[k]){
j++;k++;ne[j] = k;}else k = ne[k];}
}void dfs1(int u)
{
if(dfn1[u]) return;dfn1[u] = ++cnt1;for(int i=0;i<g1[u].size();i++) dfs1(g1[u][i]);rr1[u] = cnt1;
}void dfs2(int u)
{
if(dfn2[u]) return;dfn2[u] = ++cnt2;if(u > 0) re[cnt2] = dfn1[u - 1];else re[cnt2] = -1;for(int i=0;i<g2[u].size();i++) dfs2(g2[u][i]);rr2[u] = cnt2;
}void build(int &rt, int l, int r)
{
rt = ++idx;sum[rt] = 0;if(l == r) return;int mid = (l + r) >> 1;build(L[rt], l, mid);build(R[rt], mid + 1, r);
}void update(int &rt, int pre, int l, int r, int pos)
{
rt = ++idx;L[rt] = L[pre], R[rt] = R[pre], sum[rt] = sum[pre] + 1;if(l == r) return;int mid = (l + r) >> 1;if(pos <= mid) update(L[rt], L[pre], l, mid, pos);if(pos > mid) update(R[rt], R[pre], mid + 1, r, pos);
}int query(int ltree, int rtree, int l, int r, int ql, int qr)
{
if(l >= ql && r <= qr) return sum[rtree] - sum[ltree];int res = 0;int mid = (l + r) >> 1;if(ql <= mid) res += query(L[ltree], L[rtree], l, mid, ql, qr);if(qr > mid) res += query(R[ltree], R[rtree], mid + 1, r, ql, qr);return res;
}int main()
{
int T = 1;scanf("%d",&T);while(T--){
idx = cnt1 = cnt2 = 0;scanf("%d%d",&len,&q);for(int i=0;i<=len;i++) g1[i].clear(), g2[i].clear(), dfn1[i] = dfn2[i] = havefa1[i] = havefa2[i] = 0;scanf("%s",s);getnext();for(int i=0;i<=len;i++) if(ne[i] > 0){
g1[ne[i] - 1].push_back(i - 1);havefa1[i - 1] = 1;}reverse(s, s + len);getnext();for(int i=0;i<=len;i++) if(ne[i] > 0){
g2[len - 1 - (ne[i] - 1)].push_back(len - 1 - (i - 1));havefa2[len - 1 - (i - 1)] = 1;}for(int i=0;i<len;i++) if(!havefa1[i]) dfs1(i);for(int i=0;i<len;i++) if(!havefa2[i]) dfs2(i);build(t[0], 1, len);for(int i=1;i<=len;i++){
if(re[i] == -1) t[i] = t[i - 1];else update(t[i], t[i - 1], 1, len, re[i]);}while(q--){
int x, y;scanf("%d%d",&x,&y);x--;y = len - y;printf("%d\n",query(t[dfn2[y] - 1], t[rr2[y]], 1, len, dfn1[x], rr1[x]));}}return 0;
}