首页 > 编程语言 > 详细

2021“MINIEYE杯”中国大学生算法设计超级联赛(10)Pty loves string (border树应用 + 主席树 + dfs序)

时间:2021-09-06 23:53:54      阅读:4      评论:0      收藏:0      [点我收藏+]

题意:
给定你一个长度为\(n\)的字符串\(s\)\(m\)个询问,每次询问给定\(x,y\),问你\(s[1,x]\)\(s[n-y+1,n]\)这两个前缀后缀串拼接形成的字符串\(s‘\)在主串\(s\)中出现了几次。

思路:
首先解决这道题目前,如果大家没做过P5829,强烈推荐先做一下,\(border\)树的模板题,做过之后更好理解\(border\)应用的含义。
看到前缀和后缀,我们可以考虑一些字符串的特殊搞题方法,这里就是通过\(border\)完成一个转化。
假设拼接后子串出现在\(s\)的某个区间\([l,r]\)内,那么我们可以得到\(s_{1...x} = s_{l...l+x-1}\)\(s_{n-y+1....n} = s_{r-y+1....r}\)这两个等式,并且\((l + x - 1) + 1 = r - y +1\),这样才能保证两个子串恰好拼接。

所以现在我们的问题可以理解为,每次询问\(x,y\)后,\(s\)串有多少个位置\(a\),使得\(s_{1...x}=s_{a-x+1...a}\),即多少个位置的长度为\(x\)的后缀和前缀相等,这不就是我们对于一个串中的\(border\)的定义嘛,考虑对每个位置\(i\)由它的\(fail_i\)\(i\)连边,构造\(border\)树,那么\(x\)的子树内的点是不是都是符合条件的点,即一定存在一个长度为\(x\)的公共前后缀。

再考虑s的后缀,即找到\(s_{r-y+1...r} = s_{n-y+1...n}\),我们只需要倒序遍历\(s\),即可把后缀转化为前缀,对称来看的话(且为了保持树中节点编号大小的单调性),失配指针默认从\(n+1\)而不是\(0\)开始。倒序对每个位置\(i\)同样也是由\(fail_i\)\(i\)连边,那么满足条件的所有位置\(r-y+1\)记为\(b\),一定存在于\(n-y+1\)这个点的子树中

这样问题就变成了,每次询问分别给出两棵树上的两个点,求出这两个数中,有多少个节点\(u,v\)\(u\)属于前缀\(border\)树,\(v\)属于后缀)满足\(u + 1 = v\),即可看做求两个子树中节点值相同的点有多少个。

考虑\(dfs\)序转化成线性结构,然后主席树查询操作,把一棵数看做区间,一棵树看做值域,二维数点问题嘛。

我们对前缀的\(border\)树按照其\(dfs\)序的编号顺序建树,保证查询区间代表第一棵树的某个子树的范围。
之后类似于二维数点顺着\(x\)坐标更新\(y\)范围内的值,顺着第一棵树的节点顺序,在第二棵树代表的\(dfs\)序范围内更新信息。
那么我们对值域进行插入的时候考虑就应该是是后缀\(border\)树的\(dfs\)序了。
即我们找到\(dfn1[tim1] + 1\)(\(+1\)因为是找\(a+1=b\))这个值在后缀\(border\)树中的时间戳位置(即\(in2[dfn[tim1]+1]\))更新一下,那么我们查询的时候就查询\(y\)子树对应的时间戳的内值即可。

#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define eb emplace_back
#define MP make_pair
#define pii pair<int,int>
#define pll pair<ll,ll>
#define lson rt<<1
#define rson rt<<1|1
#define CLOSE std::ios::sync_with_stdio(false)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef double db;
const int INF = 0x3f3f3f3f;
const db eps = 1e-6;
const int N = 2e5 + 10;
char s[N];
int nex[N],renex[N],n,m;
std::vector<int>G1[N],G2[N];

void getborder() {
	nex[0] = 0,nex[1] = 0;
	for(int i = 2,j = 0;i <= n;i ++) {
		while(j != 0 && s[j+1] != s[i]) j = nex[j];
		if(s[j+1] == s[i]) ++j;
		nex[i] = j;
	}
	//倒着做 r - y + 1 一定在 n - y + 1的子树中 y为后缀长度 否则无法保证连续
	renex[n+1] = renex[n] = n + 1;
	for(int i = n - 1,j = n + 1;i >= 1;i --) {
		while(j != n + 1 && s[j-1] != s[i]) j = renex[j];
		if(s[j-1] == s[i]) --j;
		renex[i] = j;
	}
}

int dfn1[N],dfn2[N],in1[N],in2[N],siz1[N],siz2[N],tim1,tim2;
void dfs1(int u) {
	siz1[u] = 1;
	in1[u] = ++tim1;
	dfn1[tim1] = u;
	for(auto v : G1[u]) {
		dfs1(v);
		siz1[u] += siz1[v];
	}
}
void dfs2(int u) {
	siz2[u] = 1;
	in2[u] = ++tim2;
	dfn2[tim2] = u;
	for(auto v : G2[u]) {
		dfs2(v);
		siz2[u] += siz2[v];
	}
}

int tr[N*25],lc[N*25],rc[N*25],root[N],tot;
void build(int &now,int l,int r) {
	now = ++tot;
	if(l == r) { tr[now] = 0; return ;}
	int mid = (l + r) >> 1;
	build(lc[now],l,mid); build(rc[now],mid+1,r);
	tr[now] = tr[lc[now]] + tr[rc[now]];
}
void modify(int &now,int pre,int l,int r,int p) {
	tr[now = ++tot] = tr[pre],lc[now] = lc[pre],rc[now] = rc[pre];
	if(l == r) { tr[now]++; return ; }
	int mid = (l + r) >> 1;
	if(p <= mid) modify(lc[now],lc[pre],l,mid,p);
	else modify(rc[now],rc[pre],mid+1,r,p);
	tr[now] = tr[lc[now]] + tr[rc[now]]; 
}
int query(int now,int pre,int l,int r,int L,int R) {
	if(l >= L && r <= R) return tr[now] - tr[pre];
	int mid = (l + r) >> 1,ans = 0;
	if(L <= mid) ans += query(lc[now],lc[pre],l,mid,L,R);
	if(R > mid) ans += query(rc[now],rc[pre],mid+1,r,L,R);
	return ans;
}
void solve() {
	scanf("%d%d",&n,&m);
	for(int i = 0;i <= n + 1;i ++) G1[i].clear(),G2[i].clear();
	scanf("%s",s+1);
	getborder();
	// for(int i = 1;i <= n;i ++) cout << i << ": " << nex[i] << ‘\n‘;
	// for(int i = n;i >= 1;i --) cout << i << ": " << renex[i] << ‘\n‘;
	for(int i = 1;i <= n;i ++) G1[nex[i]].pb(i);
	for(int i = n;i >= 1;i --) G2[renex[i]].pb(i);
	tim1 = tim2 = 0;
	dfs1(0);
	dfs2(n+1);
	tot = 0;
	build(root[0],1,tim2);
	for(int i = 1;i <= tim1;i ++) {
		// cout << dfn1[i] << ‘ ‘ << in2[dfn1[i]+1] << "***\n";
		modify(root[i],root[i-1],1,tim2,in2[dfn1[i]+1]);
	}
	int x,y;
	// for(int i = 1;i <= tim1;i ++) cout << i << ": " << in1[i] << ‘\n‘;
	while(m--) {
		scanf("%d%d",&x,&y);
		int l = in1[x],r = in1[x] + siz1[x] - 1;
		y = n - y + 1;
		int ans = query(root[r],root[l-1],1,tim2,in2[y],in2[y]+siz2[y]-1);
		printf("%d\n",ans);
	}
}

int main() {
	int T;scanf("%d",&T);
	while(T--) solve();
	return 0;
}

2021“MINIEYE杯”中国大学生算法设计超级联赛(10)Pty loves string (border树应用 + 主席树 + dfs序)

原文:https://www.cnblogs.com/forward77/p/15231352.html

(0)
(0)
   
举报
评论 一句话评论(0
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!