[Codeforces955D]Scissors
给定两个串 \(s,t\) 整数 \(k\) ,你可以在 \(s\) 中取出任意的两个不相交的长度为 \(k\) 串,将它们按顺序拼在一起形成一个新串。
求一种取串的方案使得 \(t\) 是新串的子串。
\(|s|,|t| \leq 5 \times 10^5\)。
kmp 算出正串和反串的能匹配 \(t\) 的前/后缀最大长度。
设 \(s\) 串的前缀 \([pre_1 \dots pre_i]\) 能匹配 \(t\) 的前缀集合为 \(P\),后缀 \([suf_{i+1},suf_n]\) 能匹配 \(t\) 的后缀集合为 \(Q\),只要判断是否存在 \(x\in P,y\in Q,x, y\leq k,x+y=|s|\) 即可。
类似 AC 自动机那样建出 fail 树,那么一个点能匹配的前缀长度集合就是在 fail 树上到根的路径,在正串 fail 树上维护集合 \(P\),每次添加一个数 \(x\) 时,标记 \(k-x\) 对应在反串 fail 树上的点,每次查询反串 fail 树上一个点的祖先是否被标记。
具体实现时,标记一个点可以用子树加一,查询的时候单点查询即可。
复杂度 \(O(n \log n)\)。
#include <bits/stdc++.h>
#define dbg(...) std::cerr << "\033[32;1m", fprintf(stderr, __VA_ARGS__), std::cerr << "\033[0m"
template <class T, class U>
inline bool smin(T &x, const U &y) { return y < x ? x = y, 1 : 0; }
template <class T, class U>
inline bool smax(T &x, const U &y) { return x < y ? x = y, 1 : 0; }
using LL = long long;
using PII = std::pair<int, int>;
constexpr int N(1e6 + 5);
int n, m, k;
std::vector<int> g[N];
int in[N], out[N], cnt;
void dfs(int x) {
[x] = ++cnt;
infor (int y : g[x]) {
(y);
dfs}
[x] = cnt;
out}
int c[N];
void add(int p, int x) {
for (; p <= cnt; p += p & -p) {
[p] += x;
c}
}
int ask(int p) {
int r = 0;
for (; p; p -= p & -p) {
+= c[p];
r }
return r;
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::string s, t;
std::cin >> n >> m >> k >> s >> t;
std::vector<int> p(m), q(m + n + 1);
[0] = -1;
pfor (int i = 1, j; i < m; i++) {
for (j = p[i - 1]; j >= 0 && t[j + 1] != t[i]; j = p[j]) ;
[i] = j + (t[j + 1] == t[i]);
p}
[m - 1] = m;
q[m].push_back(m - 1);
gfor (int i = m - 2, j; i >= 0; i--) {
for (j = q[i + 1]; j < m && t[j - 1] != t[i]; j = q[j]) ;
[i] = j - (t[j - 1] == t[i]);
q[q[i]].push_back(i);
g}
for (int i = n - 1, j = m; i >= 0; i--) {
for (; j < m && t[j - 1] != s[i]; j = q[j]) ;
-= t[j - 1] == s[i];
j if (j == 0) {
if (i >= n - k && k - 1 < n - k) {
std::cout << "Yes\n" << 1 << " " << n - k + 1 << "\n";
return 0;
}
= q[j];
j }
[j].push_back(i + m + 1);
g[i + m + 1] = j;
q}
(m);
dfsstd::vector<int> vis(m);
for (int i = 0, j = -1; i < n - k; i++) {
for (; j >= 0 && t[j + 1] != s[i]; j = p[j]) ;
+= t[j + 1] == s[i];
j if (j == m - 1) {
if (i < k && k - 1 < n - k) {
std::cout << "Yes\n" << 1 << " " << n - k + 1 << "\n";
return 0;
}
= p[j];
j }
if (i < k - 1) continue;
for (int k = j; k >= m - ::k - 1 && vis[k] <= 0; k = p[k]) {
[k] = i + 1;
visif (k < ::k) {
(in[k + 1], 1), add(out[k + 1] + 1, -1);
add} else {
[k] = -vis[k];
vis}
}
if (ask(in[i + m + 2])) {
std::cout << "Yes\n";
int x = q[i + m + 2];
for (; x < m && vis[x - 1] <= 0; x = q[x]) ;
std::cout << vis[x - 1] - k + 1 << " " << i + 2 << "\n";
return 0;
}
}
std::cout << "No\n";
return 0;
}
最后修改于 2021-08-13