[Codeforces955D] Scissors

给定两个串 (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;
}