时间戳

首页 > 技术文章 > CF955D Scissors

CF955D Scissors

dysyn1314 2020-12-16 22:06 原文

CF955D Scissors

题目来源：Codeforces, Codeforces Round #471 (Div. 2), CF#471, CF955D Scissors

题目大意

题目链接

给定一个长度为 \(n\) 的串 \(s\) 和一个长度为 \(m\) 的串 \(t\)。给定一个正整数 \(k\)。

请找出 \(s\) 的两个互不重叠的、长度为 \(k\) 的子串，满足：将它们按原有顺序拼接后，得到的串中包含 \(t\)（\(t\) 是一个子串）。

数据范围：\(2\leq m\leq 2\cdot k\leq n\leq 5\times 10^5\)。

本题题解

考虑 \(s\) 里，被选出的两个长度为 \(k\) 的子串，称为关键子串 1、关键子串 2。

分两种情况：

  1. \(t\) 被完整地包含在某个关键子串中；
  2. \(t\) 在两个关键子串的拼接处。

对于情况 1，做一遍普通的 KMP 即可判断。因此以下只讨论情况 2。

枚举关键子串 1 的结尾位置 \(i\)，用 KMP 可以求出一个最大的 \(f_i\)，满足 \(s[i - f_i + 1, i] = t[1,f_i]\)。同理，枚举关键子串 2 的开头位置 \(j\)，可以求出一个最大的 \(g_j\)，满足 \(s[j,j + g_j - 1] = t[m - g_j + 1, m]\)。

如果存在一对 \(k\leq i < j\leq n - k + 1\)，满足 \(f_i + g_j = m\)，那么我们已经找出了答案。

然而，如果没找到这样的 \(i,j\)，并不一定代表无解。事实上，上述做法的误区是，数值大的 \(f_i\), \(g_j\)，并不一定最优。具体来说，当 \(k\leq i < 2k\) 时，可能存在 \(s[i - f_i +1]\) 的一个 border，由它作为 \(t\) 的前缀，去和后面拼接，能得到答案。对于 \(g\) 也是类似的。

如果枚举 \(i\)，再暴力枚举 border，由于 border 的数量最大有 \(\mathcal{O}(\text{串长})\) 个（例如串 \(\texttt{aaa...a}\)），这样时间复杂度最坏为 \(\mathcal{O}(k^2)\)，无法通过本题。

考虑优化这个“暴力跳 border”的过程。设 \(t[1,x]\) 的 border 长度为 \(\text{fail}(x)\)（与 KMP 算法里的定义是一样的），对于所有 \(1\leq x\leq m\) 如果 \(\text{fail}(x)\neq 0\)，我们从 \(\text{fail}(x)\) 向 \(x\) 连一条边，发现可以得到一个有根树森林。“暴力跳 border”，就相当于在枚举一个节点 \(x\) 的所有祖先。因此可以用树链剖分优化。更具体地，由于一前一后各做一次 KMP，实际上需要建出两个森林。

考虑从小到大枚举 \(j\)，每次 \(i = j - 1\) 会成为一个新出现的、可能的 \(i\)，我们把 \(f_i\) 在树上的所有祖先打上标记。然后要对 \(g_j\) 的所有祖先进行查询。通过树链剖分和 dfs 序，把树上问题转化为序列问题后，问题可以形式化地描述为：

有两个排列 \(p_{1\dots m}, q_{1\dots m}\)（也就是两个森林的 dfs 序序列），需要支持若干次操作。操作分为如下两种：

  1. 给定区间 \([l,r]\)，把 \(p_{l\dots r}\) 里所有数值打上标记。
  2. 给定区间 \([l,r]\)，查询 \(q_{l\dots r}\) 里是否存在被标记过的数值。

这个问题并不难。考虑离线，预处理出每个数值第一次被标记的时间，这可以通过倒序遍历操作，转化为区间覆盖问题。然后查询就变成了区间最小值查询，可以用 ST 表实现。

如果用线段树做区间覆盖，因为外层还要跳 \(\mathcal{O}(\log n)\) 条重链，总时间复杂度是 \(\mathcal{O}(n\log^2 n)\)（\(n,m,k\) 同阶）。可以通过本题，但不够优秀。进一步观察发现，区间覆盖操作是静态的（所有修改发生在询问之前），因此可以用并查集维护。总时间复杂度优化为 \(\mathcal{O}(n\log n)\)。

参考代码

建议使用快速输入、输出，详见本博客公告。

// problem: CF955D
#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define mk make_pair
#define lob lower_bound
#define upb upper_bound
#define fi first
#define se second
#define SZ(x) ((int)(x).size())

typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;

template<typename T> inline void ckmax(T& x, T y) { x = (y > x ? y : x); }
template<typename T> inline void ckmin(T& x, T y) { x = (y < x ? y : x); }

const int MAXN = 5e5;
const int LOG = 18;
const int INF = 1e9;

class KMP {
public:
	int fail[MAXN + 5], match[MAXN + 5];
	void get_fail(const char* t, int m) {
		fail[1] = 0;
		for (int i = 2, j = 0; i <= m; ++i) {
			while (j && t[i] != t[j + 1])
				j = fail[j];
			if (t[i] == t[j + 1])
				++j;
			
			fail[i] = j;
			// cerr << j << " \n"[i == m];
		}
	}
	void get_match(const char* s, const char* t, int n, int lim) {
		for (int i = 1, j = 0; i <= n; ++i) {
			while (j && (s[i] != t[j + 1] || j >= lim))
				j = fail[j];
			if (s[i] == t[j + 1])
				++j;
			
			match[i] = j;
			// cerr << j << " \n"[i == n];
		}
	}
	KMP() {}
};

class Tree {
public:
	struct EDGE { int nxt, to; } edge[MAXN * 2 + 5];
	int head[MAXN + 5], tot;
	inline void add_edge(int u, int v) { edge[++tot].nxt = head[u]; edge[tot].to = v; head[u] = tot; }
	
	int fa[MAXN + 5], sz[MAXN + 5], son[MAXN + 5], dep[MAXN + 5];
	void dfs1(int u) {
		sz[u] = 1;
		for (int i = head[u]; i; i = edge[i].nxt) {
			int v = edge[i].to;
			if (v == fa[u])
				continue;
			fa[v] = u;
			dep[v] = dep[u] + 1;
			dfs1(v);
			sz[u] += sz[v];
			if (!son[u] || sz[v] > sz[son[u]])
				son[u] = v;
		}
	}
	int top[MAXN + 5], dfn[MAXN + 5], ofn[MAXN + 5], rev[MAXN + 5], cnt_dfn;
	void dfs2(int u, int t) {
		top[u] = t;
		dfn[u] = ++cnt_dfn;
		rev[cnt_dfn] = u;
		if (son[u])
			dfs2(son[u], t);
		for (int i = head[u]; i; i = edge[i].nxt) {
			int v = edge[i].to;
			if (v == fa[u] || v == son[u])
				continue;
			dfs2(v, v);
		}
		ofn[u] = cnt_dfn;
	}
	bool is_anc(int anc, int v) {
		return dfn[anc] <= dfn[v] && ofn[anc] >= dfn[v];
	}
	Tree() {}
};

class StaticRangeCover {
private:
	int len;
	int fa[MAXN + 5], sz[MAXN + 5], mx[MAXN + 5], res[MAXN + 5];
	vector<pair<pii, int> > vec;
	int get_fa(int u) {
		return (u == fa[u]) ? u : (fa[u] = get_fa(fa[u]));
	}
	void unite(int u, int v) {
		u = get_fa(u);
		v = get_fa(v);
		if (u != v) {
			if (sz[u] > sz[v])
				swap(u, v);
			fa[u] = v;
			sz[v] += sz[u];
			mx[v] = max(mx[v], mx[u]);
		}
	}
	void jump_and_cover(int l, int r, int val) {
		for (int i = l; i <= r; ++i) {
			i = mx[get_fa(i)];
			if (i > r) {
				break;
			}
			res[i] = val;
			unite(i, r + 1);
		}
	}
public:
	void build(int _len) {
		len = _len;
		for (int i = 1; i <= len + 1; ++i) {
			fa[i] = i;
			sz[i] = 1;
			mx[i] = i;
			res[i] = INF;
		}
	}
	void range_cover(int l, int r, int v) {
		vec.pb(mk(mk(l, r), v));
	}
	void get_res(int* _res) {
		for (int i = SZ(vec) - 1; i >= 0; --i) {
			jump_and_cover(vec[i].fi.fi, vec[i].fi.se, vec[i].se);
		}
		for (int i = 1; i <= len; ++i) {
			_res[i] = res[i];
		}
	}
	StaticRangeCover() {}
};

class RangeMinQuery {
private:
	int _log2[MAXN + 5];
	pii st[MAXN + 5][LOG + 1];
public:
	void build(int* a, int n) {
		_log2[0] = -1;
		for (int i = 1; i <= n; ++i) {
			_log2[i] = _log2[i >> 1] + 1;
			st[i][0] = mk(a[i], i);
		}
		for (int j = 1; j <= LOG; ++j) {
			for (int i = 1; i + (1 << (j - 1)) <= n; ++i) {
				st[i][j] = min(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
			}
		}
	}
	pii rmq(int l, int r) {
		int k = _log2[r - l + 1];
		return min(st[l][k], st[r - (1 << k) + 1][k]);
	}
	int rmq_val(int l, int r) { return rmq(l, r).fi; }
	int rmq_pos(int l, int r) { return rmq(l, r).se; }
	RangeMinQuery() {}
};

int n, m, K;
char s[MAXN + 5], t[MAXN + 5];

KMP kmp, kmp_rev;
Tree tree, tree_rev;

StaticRangeCover DSU;
RangeMinQuery RMQ;

void cover_anc(int u, int tim) {
	while (u) {
		int l = tree.dfn[tree.top[u]], r = tree.dfn[u];
		DSU.range_cover(l, r, tim);
		u = tree.fa[tree.top[u]];
	}
}

int first_cov_tim[MAXN + 5];
int arr[MAXN + 5];
void query_anc(int u, int tim) {
	// u 的祖先, 有没有人在第 tim 时刻之前(严格小于)被覆盖了?
	while (u) {
		int l = tree_rev.dfn[tree_rev.top[u]], r = tree_rev.dfn[u];
		if (RMQ.rmq_val(l, r) < tim) {
			cout << "Yes" << endl;
			int x = tree_rev.rev[RMQ.rmq_pos(l, r)] - 1;
			for (int i = K; i < tim; ++i) {
				int v = kmp.match[i];
				if (v != 0 && tree.is_anc(x, v)) {
					cout << i - K + 1 << " " << tim << endl;
					exit(0);
				}
			}
			assert(0);
		}
		u = tree_rev.fa[tree_rev.top[u]];
	}
}
int main() {
	cin >> n >> m >> K;
	cin >> (s + 1);
	cin >> (t + 1);
	
	kmp.get_fail(t, m);
	kmp.get_match(s, t, n, min(m, K));
	reverse(s + 1, s + n + 1);
	reverse(t + 1, t + m + 1);
	kmp_rev.get_fail(t, m);
	kmp_rev.get_match(s, t, n, min(m, K));
	
	if (m <= K) {
		for (int i = m; i <= n - K; ++i) {
			if (kmp.match[i] == m) {
				cout << "Yes" << endl;
				cout << max(1, i - K + 1) << " " << n - K + 1 << endl;
				return 0;
			}
		}
		for (int i = K + 1; i <= n - m + 1; ++i) {
			if (kmp_rev.match[n - i + 1] == m) {
				cout << "Yes" << endl;
				cout << 1 << " " << min(i, n - K + 1) << endl;
				return 0;
			}
		}
	}
	
	for (int i = 2; i <= m; ++i) {
		if (kmp.fail[i]) {
			tree.add_edge(kmp.fail[i], i);
		}
		if (kmp_rev.fail[i]) {
			tree_rev.add_edge(m - kmp_rev.fail[i] + 1, m - i + 1);
			// cerr << "addedge(rev) " << m - kmp_rev.fail[i] + 1 << " " << m - i + 1 << endl;
		}
	}
	for (int i = 1; i <= m; ++i) {
		if (!tree.fa[i]) {
			tree.dfs1(i);
			tree.dfs2(i, i);
		}
	}
	for (int i = m; i >= 1; --i) {
		if (!tree_rev.fa[i]) {
			tree_rev.dfs1(i);
			tree_rev.dfs2(i, i);
		}
	}
	
	DSU.build(m);
	for (int i = n - K; i >= K; --i) {
		if (kmp.match[i] != 0) {
			int u = kmp.match[i];
			// cerr << "cover " << u << " " << i << endl;
			cover_anc(u, i);
		}
	} // 倒序添加, 预处理出每个位置第一次被覆盖是在什么时间
	
	DSU.get_res(first_cov_tim);
	for (int i = 1; i <= m; ++i) {
		if (tree_rev.rev[i] != 1) {
			arr[i] = first_cov_tim[tree.dfn[tree_rev.rev[i] - 1]];
			// cerr << arr[i] << endl;
		}
	}
	RMQ.build(arr, m);
	
	for (int i = K + 1; i <= n - K + 1; ++i) {
		if (kmp_rev.match[n - i + 1] != 0) {
			int u = m - kmp_rev.match[n - i + 1] + 1;
			// cerr << "query " << u << " " << i << endl;
			assert(u != 1);
			query_anc(u, i);
		}
	}
	cout << "No" << endl;
	return 0;
}

推荐阅读