Problem Description
Pty has a string S of length n consisting of lowercase English letters. He denotes the value of string T as the number of occurrences of T in string S.
Now he has Q queries, for each query he gives you x,y. Let the string T be the concatenation of the prefix of length x in the string S and its suffix of length y. He wants you to tell him the value of T.
Input
An integer T in the first line indicates the number of tests.
For each test,first line contains two integer n,Q - the length of S and the number of queries.
The second line contains string S of length n consisting of lowercase English letters.
For the next Q lines, each line contains two integers x,y.
1≤T≤5,1≤n,Q≤2×105,1≤x,y≤n
Output
For each test,output Q lines in total.
For each query, print the answer in one line.
Sample Input
1
6 3
ababaa
1 1
2 1
3 1
Sample Output
1
2
1
Debug一年终于把这个题过了，原因在于询问次数q打成了n。。。
首先一看问的是串的出现次数，可能会想到kmp，但暴力kmp显然不可做。又注意到每次的询问给出的x和y和原串前后缀有关，就考虑从前缀和后缀这里入手。对于这个题，设给定的字符串为(s)，每个询问给出一对前后缀(s[1,x])和(s[n - y + 1, n])，不妨设其拼起来后在(s)的([p, q])这个位置出现了，那么(s[1,x])和(s[p, p + x - 1])相等，(s[n - y + 1, n])和(s[q - y + 1,q])相等，同时有(q - y + 1 = (p + x - 1) + 1)。直接的思想就是找所有和(s[1, x])相等的子串以及所有和(s[n - y + 1, n])相等的子串检查他们能否拼接在一起。那么怎么找呢？这时就需要用到(Border)这个知识点了，相关知识可以参考洛谷P5829这道题。我们正着和反着分别建出(next)树以后，会发现(p + x - 1)一定在(x)的子树，(q - y + 1)一定在(n - y + 1)的子树（因为y表示的是后缀长度）。举个例子，设(s=‘ababab’)，(x = 2)，那么(next[4])和(next[6])都为2，都在2的子树里，观察也可以发现后两个ab都和第一个ab（前缀）一样。也可以自己构造一下加深理解（关键是要知道(Border)的(Border)还是(Border)以及理解(next)树的具体含义）。
所以现在问题转化为给出两棵树，树上每个点都有一个值，然后每次询问给出x和y两个子树，问两棵子树中有多少个点对((a, b))满足(a + 1 = b)（因为是正着和倒着建的next树，所以有这个关系）。因为树上问题可以通过(dfs)序转化为序列问题，这就类似给出两个序列，询问子列的交集。此时就需要用到主席树了。建出两棵(next)树以后分别进行(dfs)求出来(dfs)序，然后我们沿着第一棵树的(dfs)序建主席树。这里有一个很关键的问题就是两棵树的形状可能不一样，怎么处理节点相等这个对应关系。这里有一个很巧妙的方式就是在处理(dfs)序的时候同时获得第一棵树上某个dfs序所对应的真实的值（即下标）存到id数组里，然后对于1~n + 1遍历的时候（为什么是n + 1？因为next树的根是0号节点，所以dfs序是1~n + 1），增加的位置是(dfn2[id1[i] + 1])。(id1[i] + 1)就是对应的(a + 1 = b)这个关系，然后(dfn2[id1[i] + 1])就把对应的b转到第二棵树的相应的dfs序位置了。建好树以后不断读入查询即可，查询的就是在x这个子树对应的区间里，有多少y这个子树对应区间内的(dfn)值落进去了（因为已经把下标的对应关系转为了(dfn)值的对应关系），常规的主席树套路。
#include <bits/stdc++.h>
#define N 1000005
using namespace std;
int n, q;
char s[N];
int nxt1[N], nxt2[N];
int head1[N], ver1[2 * N], Next1[2 * N], tot1 = 0;
int head2[N], ver2[2 * N], Next2[2 * N], tot2 = 0;
void add1(int x, int y) {
ver1[++tot1] = y, Next1[tot1] = head1[x], head1[x] = tot1;
}
void add2(int x, int y) {
ver2[++tot2] = y, Next2[tot2] = head2[x], head2[x] = tot2;
}
vector<int> node1[N], node2[N];
void getnxt1() {
nxt1[1] = 0;
int n = strlen(s + 1);
for(int i = 2, j = 0; i <= n; i++) {
while(j != 0 && s[i] != s[j + 1]) j = nxt1[j];
if(s[i] == s[j + 1]) j++;
nxt1[i] = j;
}
for(int i = 1; i <= n; i++) {
add1(nxt1[i], i);
}
}
void getnxt2() {
int n = strlen(s + 1);
nxt2[n] = n + 1;
for(int i = n - 1, j = n + 1; i >= 1; i--) {
while(j != n + 1 && s[i] != s[j - 1]) j = nxt2[j];
if(s[i] == s[j - 1]) j--;
nxt2[i] = j;
}
for(int i = 1; i <= n; i++) {
add2(nxt2[i], i);
}
}
int dfn1[N], dfn2[N], id1[N], id2[N], sz1[N], sz2[N], cnt1 = 0, cnt2 = 0;
int ed1[N], ed2[N];
void dfs1(int x, int pre) {
sz1[x] = 1;
dfn1[x] = ++cnt1;
id1[cnt1] = x;
for(int i = head1[x]; i; i = Next1[i]) {
int y = ver1[i];
if(y == pre) continue;
dfs1(y, x);
sz1[x] += sz1[y];
}
ed1[x] = cnt1;
}
void dfs2(int x, int pre) {
sz2[x] = 1;
dfn2[x] = ++cnt2;
id2[cnt2] = x;
for(int i = head2[x]; i; i = Next2[i]) {
int y = ver2[i];
if(y == pre) continue;
dfs2(y, x);
sz2[x] += sz2[y];
}
ed2[x] = cnt2;
}
int cnt = 0;//总的节点数
int sum[N * 20], L[N * 20], R[N * 20];//主席树一定不能吝啬空间
int T[N];
int build(int l, int r) {
int rt = ++cnt;
sum[rt] = 0;
int mid = (l + r) >> 1;
if(l < r) {
L[rt] = build(l, mid);
R[rt] = build(mid + 1, r);
}
return rt;
}
int modify(int pre, int l, int r, int x) {
int rt = ++cnt;
L[rt] = L[pre]; R[rt] = R[pre];
sum[rt] = sum[pre] + 1;
if(l < r) {
int mid = (l + r) >> 1;
if(x <= mid) L[rt] = modify(L[pre], l, mid, x);
//注意这里是x <= mid, 而不是线段树常见写法
//因为这是对权值建立的线段树！
else R[rt] = modify(R[pre], mid + 1, r, x);
}
return rt;
}
int query(int u, int v, int LFT, int RT, int l, int r) {
if(LFT > r || RT < l) return 0;
int x = sum[v] - sum[u];
if(l >= LFT && r <= RT) return x;
int mid = (l + r) >> 1;
return query(L[u], L[v], LFT, RT, l, mid) + query(R[u], R[v], LFT, RT, mid + 1, r);
}
int main() {
int t;
cin >> t;
while(t--) {
tot1 = tot2 = 0;
cnt1 = cnt2 = 0;
cnt = 0;
memset(s, 0, sizeof(s));
memset(head1, 0, sizeof(head1));
memset(head2, 0, sizeof(head2));
scanf("%d%d", &n, &q);
scanf("%s", s + 1);
getnxt1();
getnxt2();
dfs1(0, -1);
dfs2(n + 1, -1);
T[0] = build(1, n + 1);
for(int i = 1; i <= n + 1; i++) {
T[i] = modify(T[i - 1], 1, n + 1, dfn2[id1[i] + 1]);
}
for(int i = 1; i <= q; i++) {
int x, y;
cin >> x >> y;
y = n - y + 1;
cout << query(T[dfn1[x] - 1], T[ed1[x]], dfn2[y], ed2[y], 1, n + 1) << endl;
}
}
return 0;
}