给定两个串 (s,t) 整数 (k) ,你可以在 (s) 中取出任意的两个不相交的长度为 (k) 串，将它们按顺序拼在一起形成一个新串。
求一种取串的方案使得 (t) 是新串的子串。
(|s|,|t| leq 5 imes 10^5)。
kmp 算出正串和反串的能匹配 (t) 的前/后缀最大长度。
设 (s) 串的前缀 ([pre_1 dots pre_i]) 能匹配 (t) 的前缀集合为 (P)，后缀 ([suf_{i+1},suf_n]) 能匹配 (t) 的后缀集合为 (Q)，只要判断是否存在 (xin P,yin Q,x, yleq 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 << " 33[32;1m", fprintf(stderr, __VA_ARGS__), std::cerr << " 33[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) {
in[x] = ++cnt;
for (int y : g[x]) {
dfs(y);
}
out[x] = cnt;
}
int c[N];
void add(int p, int x) {
for (; p <= cnt; p += p & -p) {
c[p] += x;
}
}
int ask(int p) {
int r = 0;
for (; p; p -= p & -p) {
r += c[p];
}
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);
p[0] = -1;
for (int i = 1, j; i < m; i++) {
for (j = p[i - 1]; j >= 0 && t[j + 1] != t[i]; j = p[j]) ;
p[i] = j + (t[j + 1] == t[i]);
}
q[m - 1] = m;
g[m].push_back(m - 1);
for (int i = m - 2, j; i >= 0; i--) {
for (j = q[i + 1]; j < m && t[j - 1] != t[i]; j = q[j]) ;
q[i] = j - (t[j - 1] == t[i]);
g[q[i]].push_back(i);
}
for (int i = n - 1, j = m; i >= 0; i--) {
for (; j < m && t[j - 1] != s[i]; j = q[j]) ;
j -= t[j - 1] == s[i];
if (j == 0) {
if (i >= n - k && k - 1 < n - k) {
std::cout << "Yes
" << 1 << " " << n - k + 1 << "
";
return 0;
}
j = q[j];
}
g[j].push_back(i + m + 1);
q[i + m + 1] = j;
}
dfs(m);
std::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]) ;
j += t[j + 1] == s[i];
if (j == m - 1) {
if (i < k && k - 1 < n - k) {
std::cout << "Yes
" << 1 << " " << n - k + 1 << "
";
return 0;
}
j = p[j];
}
if (i < k - 1) continue;
for (int k = j; k >= m - ::k - 1 && vis[k] <= 0; k = p[k]) {
vis[k] = i + 1;
if (k < ::k) {
add(in[k + 1], 1), add(out[k + 1] + 1, -1);
} else {
vis[k] = -vis[k];
}
}
if (ask(in[i + m + 2])) {
std::cout << "Yes
";
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 << "
";
return 0;
}
}
std::cout << "No
";
return 0;
}