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