P3785 SOL

OneLastNOIP · 2026-05-03 14:57:40 · 题解

0x01 简要思路

首先根据题目中把 T 划成三段可以猜测，大致思路是按照 T 拆成三段的顺序分讨。不妨设 S=123，1,2,3 分别代表三个子串。

0x02 T=123

直接判断两串是否相等即可。

0x03 T=312/231

前置知识：KMP。

显然这时两串循环同构，那么我们将 倍长，之后用 S 去匹配这个倍长串，假设 [i,i+n-1] 是我们匹配到的子串，则答案是 [i,n] 和 [1, i - 1] 选一段拆掉，注意不能把长度为 1 的段拆掉。

0x04 T=213

前置知识：KMP、Z 函数。

这种情况下 T 和 S 拥有公共的后缀，不妨枚举这个后缀，然后考虑判断这两个前缀是否合法。考虑到这种情况下 S=123,T=213，那么可以在 T 上匹配 S 的前缀，对于一个位置 i，若其匹配的其中一个前缀 S[1:j] 是合法的，当且仅当：

可以发现第二条限制和 Z 函数所求的东西很像，因此做法是：

• 对 T\#S 做 Z 函数，其中 \# 为特殊字符。
• 对 S 建立 KMP 自动机，对于每一个前缀 [1,i]，用 Z 函数做出 S[i + 1, n] 和 T 的 LCP，那么利用到 [1,i] 的最长的满足 21 格式的 T 的前缀就是 LCP+[1,i]，借此我们能够求出匹配到 S 某个位置时，T 中最大的合法位置，且若小于这个位置，同样必然满足,直接判断即可。

0x05 T=132

直接把上一种做法对称一下即可，我代码里就是把 S 和 T reverse 后做 213 的情况。

0x06 T=321

有一个非常神秘的构造：把 S reverse 一下之后与 T 交错排列，得到形如 S_1T_nS_2T_{n-1}\cdots S_nT_1 的序列，则答案中的每一个字串都对应新序列的一个 偶回文串。于是问题转化为一个串能否划分为三个偶回文串。有一个很牛的结论是：一个串若能划为两个偶回文串，那么其中有一个必然是其最长回文前/后缀，那么只要做一下马拉车就能判定一个前缀能否划分为两个偶回文串，一个后缀是否是回文串。枚举前缀即可。

然后就是关于这个结论的证明：

引理 S=A_1A_2=B_1B_2=C_1C_2，且 |A_1|<|B_1|<|C_1|，A_2,B_1,B_2,C_1 是回文串，则 A_1,C_2 亦是回文串。

证明 设 C_1=B_1X，则 X 为 B_2 的前缀，所以 X^R 为 B_2 的后缀。

由于 A_2 也是回文串，所以 X 是 A_2 的前缀，所以 A_1X 是 C_1 的前缀。

又由于 B_1 和 C_1 都是回文串，则根据回文串 C_1 有回文前缀 B_1，那么有一个结论是 C_1 存在长度为 |X| 的周期，所以 C_1 为 X^{\infty} 的后缀，那么我们设 C_1=WX^{\#}，A_1X=WX^iYX，C_1 = WX^iYXZX^j，则 WX^iYXZ 为 X^{\infty} 的后缀，所以 YXZ 为 X 的整数倍，由于 |Y|,|Z|<|X|，所以 YXZ=XX，所以 |Y|+|Z|=|X|,X=YZ=ZY，A_1=WYZ\cdots YZYZY，W 为 X 的后缀因此必然为 YZ 的后缀，所以 A_1 为 X^{\infty} 的后缀。

因为 B_1 是回文串，所以 A_1 同时也是 X^{R\infty} 的前缀，所以 A_1 也是回文串，同理 C_2 是回文串。证毕。

关于结论的证明：设 |C_1|=2a，|B_1|=2b，由两者都是回文串，C_1[1:2a-2b]=X^R,B_1[4b-2a+1,2b]=X,C_1[2a-2b+1:4a-4b]=X^R,B_1[6b-4a + 1:4b-2a]=X，归纳可证。

有这个引理之后，不难推出必然有包含最长回文前/后缀的划分方案。

0x7F Code

# include <bits/stdc++.h>
# define rep(i, a, b) for(int i = (a);i <= (b);i ++)
# define lop(i, a, b) for(int i = (a);i <  (b);i ++)
# define dwn(i, a, b) for(int i = (a);i >= (b);i --)
# define int64 long long
# define ___main signed main()
# define f64 double
# define f32 float
# define f128 long double
# define int128 __int128
# define i128 ((__int128)1)
# define int32 signed
# define un unsigned
# define int16 short
# define int8 char
# define ret return
# define inl inline 
# define reg register
# define fn void
# define elif else if
# define pb push_back
# define pp pop_back
using std::cout;
using std::cin;
# define CASES() int T;cin >> T;while(T--)
# define FaILurEg(s) freopen(s".in","r",stdin);freopen(s".out","w",stdout)
#if defined(_MSC_VER)
#  define FORCE_INLINE __forceinline
#else
#  define FORCE_INLINE __attribute__((always_inline)) inline
#endif
namespace packin {
template<typename T>struct _Arr {T *arr;int size;
FORCE_INLINE T& operator [](int i) {ret arr[i];}};
template<typename T>FORCE_INLINE fn read(T &x) {cin >> x;}
template<typename T>FORCE_INLINE fn read(_Arr<T>a) {rep(i, 1, a.size) cin >> a.arr[i];}
template<typename T>FORCE_INLINE fn read(T *a, int siz) {rep(i, 1, siz) cin >> a[i];}
template<typename T, typename... Args>FORCE_INLINE void read(T &x, Args&... args) {read(x);read(args...);}
inline void print_impl(const char* s) {while (*s) {cout << *s++;}}
template<typename T, typename... Args>inline void print_impl(const char* s, const T& x, const Args&... args) {while (*s) {if (s[0] == '{' && s[1] == '}') {cout << x;print_impl(s + 2, args...);return;}cout << *s++;}}
template<typename... Args>inline void print(const char* s, const Args&... args) {print_impl(s, args...);}
inline void error_impl(const char*s){while(*s)std::cerr<<*s++;}template<class T,class...A>inline void error_impl(const char*s,const T&x,const A&...a){while(*s){if(s[0]=='{'&&s[1]=='}'){std::cerr<<x;error_impl(s+2,a...);return;}std::cerr<<*s++;}}template<class...A>inline void error(const char*s,const A&...a){error_impl(s,a...);}
}
template<typename T>FORCE_INLINE T min(T a, T b) {ret (a < b)?a:b;}
template<typename T>FORCE_INLINE T max(T a, T b) {ret (a > b)?a:b;}
int Q;
int n, m;
using namespace packin;

typedef std::pair<int,int> pii;
typedef std::tuple<int, pii, pii, pii > Atp;

std::vector<int> S, T;

Atp MA(bool f, pii a, pii b, pii c) { ret std::make_tuple(f, a, b, c);}

Atp case123 (){
   rep(i, 0, n - 1)  
      if(S[i] != T[i]) ret MA(0, (pii){1, 1}, (pii){2, 2}, (pii){3, n});
   ret MA(1, (pii){1, 1}, (pii){2, 2}, (pii){3, n});
}
int Case, Cnt;

void getPI(std::vector<int> &spi) {
   spi.clear();
   int j = 0; spi.pb(0);
   rep(i, 1, n - 1) {
      while(j && S[i] != S[j]) j = spi[j - 1];
      if(S[i] == S[j]) j ++;
      spi.pb(j);
   }
}

// T = 312  S = 123
// T' = 312312 / 231231
/*
这种情况代表 S 和 T 循环同构，将 T 倍长后用 KMP 即可
*/
Atp 
case312() {
   std::vector<int> tt;
   tt = T;for(auto t : T) tt.pb(t);
   std::vector<int> spi;
   getPI(spi);
   //std::cerr << "test1\n";
   int j = 0;
   rep(i, 0, 2 * n - 1) {
      while(j && (j == n || S[j] != tt[i])) j = spi[j - 1];
      if(S[j] == tt[i]) j ++;
      if(j == n){
         if(i == n) 
            ret MA(1, (pii{2, n - 1}), (pii{n, n}), (pii{1,1}));
         else
            ret MA(1, (pii{i - n + 2, n}), (pii{1, 1}), (pii(2, i - n + 1))); }
   }
   //std::cerr << "test2\n";
   ret MA(0, (pii{1, 1}), (pii{2, 2}), (pii{3, n}));
}

//T = 213/132
// S = 123    Z 213#123
// KMP to do  s#T  123#213
/*
以 213 为例， 我们枚举公共的前后缀，然后对于 S 的每个后缀维护：
   其与 T 的最长公共前缀，然后就能求出若匹配到 S 的某个位置，我们是否能让当前的 前缀成为一个合法的 2-1 序列（注意维护 FAIL ）
*/
void getZ(std::vector<int> &s, std::vector<int> &z) {
   int l = 0, r = 0; z.clear(); z.pb(0);
   rep(i, 1, (int)s.size() - 1) {
      if(i <= r) z.pb(min(r - i + 1, z[i - l]));
      else z.pb(0);
      while(i + z[i] < (int)s.size() && s[z[i]] == s[i + z[i]]) 
         z[i] ++;
      if(i + z[i] - 1 > r)
         l = i, r = i + z[i] - 1;
   }
}
Atp 
case213() {
   std::vector<int> tt = T;tt.pb(-1);
   for(auto s : S) tt.pb(s);
   std::vector<int> z;
   getZ(tt, z);
   z.pb(0);
   z.pb(0);
   std::vector<int> spi, mx, mxl;
   getPI(spi);
   rep(i, 0, (int)S.size() - 1) 
      if(spi[i])
         mx.pb(max(i + z[i + n + 2], mx[spi[i] - 1])),
         mxl.pb((z[i + n + 2] + i >= mx[spi[i] - 1])?i + 1: mxl[spi[i] - 1]);
      else
         mx.pb(z[i + n + 2] + i), mxl.pb(i + 1);
   std::vector<int> pos;
   int j = 0;
   rep(i, 0, (int)T.size() - 1) {
      //KMP
      while(j && (j == n || S[j] != T[i])) j = spi[j - 1];
      if(S[j] == T[i]) j ++;
      pos.pb(j - 1);
   }
   if(T.back() != S.back()) ret MA(0, (pii{1, 1}), (pii{2, 2}), (pii{3, n}));
   dwn(i, (int)T.size() - 2, 0) 
      if(T[i + 1] == S[i + 1])
         if(pos[i] != -1 && mx[pos[i]] >= i)  // [i - mxl[pos[i]] + 1, i + 1], [1, i - mxl[pos[i]] + 1], [i + 2, n]
            ret MA(1, (pii{i - mxl[pos[i]] + 2, i + 1}), (pii{1, i - mxl[pos[i]] + 1}), (pii{i + 2, n}));
         else;
      else break;
   ret MA(0, (pii{1, 1}), (pii{2, 2}), (pii{3, n}));
}
// T = 132 -> 
FORCE_INLINE void rev(pii &p) {p.first = n + 1 - p.first, p.second = n + 1 - p.second;std::swap(p.first, p.second);}
Atp 
case132() {
   std::reverse(S.begin(), S.end());
   std::reverse(T.begin(), T.end());
   auto rett = case213();
   std::reverse(S.begin(), S.end());
   std::reverse(T.begin(), T.end());
   std::swap(std::get<1>(rett), std::get<3>(rett));
   rev(std::get<1>(rett));
   rev(std::get<2>(rett));
   rev(std::get<3>(rett));
   ret rett;
}

/*
321 
第一部是把T翻转，两个串归并起来，检验其是否能拆成三个偶回文串
根据引理，我们只要枚举最后一个回文串，维护剩下那个串能否被覆盖
*/

void manacher(std::vector<int> &s, std::vector<int> &r, std::vector<int> &bks, int n) {
   int L = 0, R = (s[0] == s[1]);
   r.pb(R);
   rep(i, 1, n - 1) {
      if(i >= R) {
         int t = 0;
         while(i + t + 1 <= n - 1 && s[i + t + 1] == s[i - t])
            t ++;
         r.pb(t);
         L =  i - t + 1;
         R = i + t;
      }  
      else {
         int mirror = L + R - 1 - i;
         int t = std::min(R - i, r[mirror]); 
         while (i - t >= 0 && i + t + 1 < n && s[i - t] == s[i + t + 1])
            ++t;
         r.push_back(t);
         if (i + t > R) {
            L = i - t + 1;
            R = i + t;
         }
      }
      if(R == n - 1 && i != n - 1)
         bks.pb(i - r[i]);
   }
}

bool isR(int l, int r, std::vector<int> &R) {
   int mid = (l + r) >> 1;
   if(R[mid] >= mid - l + 1)
      ret true;
   ret false;
}  

Atp 
case321() {
   std::vector<int> tt, R, B;
   rep(i, 0, n - 1)
      tt.pb(T[i]), tt.pb(S[n - 1 - i]);
   manacher(tt, R, B, 2 * n);
   int r0 = 0, r1 = 0;
   std::vector<int>pre;
   int Rr = 0;
   pre.pb(-1);
   rep(i, 0, 2 * n - 2) if(i & 1) {
      if(r0) if(isR(r0 + 1, i, R) && isR(i + 1, 2 * n - 1, R)) 
         ret MA(1, pii(i / 2 + 2, n), pii(r0 / 2 + 2, i / 2 + 1), pii(1, r0 / 2 + 1));  
      if(r1) if(isR(r1 + 1, i, R) && isR(i + 1, 2 * n - 1, R)) 
         ret MA(1, pii(i / 2 + 2, n), pii(r1 / 2 + 2, i / 2 + 1), pii(1, r1 / 2 + 1)); 
      if(pre.size() > i&& pre[i] != -1) if(isR(0, pre[i] - (i - pre[i]), R) && isR(i + 1, 2 * n - 1, R))
         ret MA(1, pii(i / 2 + 2, n), pii((pre[i] - (i - pre[i])) / 2 + 2, i / 2 + 1), pii(1, (pre[i] - (i - pre[i])) / 2 + 1)); 
      if(!r0 && isR(0, i, R)) r0 = r1 = i;
      if(isR(0, i, R)) r1 = i;
      if(i + R[i] > Rr && i - R[i] + 1 > 0) {
      rep(j, Rr + 1, i)
         pre.pb(-1);
      rep(j, max(i + 1, Rr + 1), i + R[i])
         pre.pb(i);
      Rr = i + R[i];
   }
   } else if(i + R[i] > Rr && i - R[i] + 1 > 0) {
      rep(j, Rr + 1, i)
         pre.pb(-1);
      rep(j, max(i + 1, Rr + 1), i + R[i])
         pre.pb(i);
      Rr = i + R[i];
   }
   ret MA(0, (pii{1, 1}), (pii{2, 2}), (pii{3, n}));
}

# define PrtAns print("YES\n{} {}\n{} {}\n{} {}\n", std::get<1>(Ans).first, std::get<1>(Ans).second, std::get<2>(Ans).first, std::get<2>(Ans).second, std::get<3>(Ans).first, std::get<3>(Ans).second);
# define Geet std::get<0>(Ans) == 1

void TCS() {
   cin  >> n >> m;
   S.clear(); T.clear();
   rep(i, 1, n) {
      int x; cin >> x;
      S.pb(x);
   }
   rep(i, 1, n) {
      int x; cin >> x;
      T.pb(x);
   }
   auto Ans = case123();
   if(Geet) {
      print("YES\n1 1\n2 2\n3 {}\n", n);
      ret;
   }
   Ans = case312();
   if(Geet) {PrtAns;ret;}
   Ans = case213();
   if(Geet) {PrtAns;ret;}
   Ans = case132();
   if(Geet) {PrtAns;ret;}
   Ans = case321();
   if(Geet) {PrtAns;ret;}
   cout << "NO\n";
}
___main {
   FaILurEg("string");
      int st = clock();
   std::ios::sync_with_stdio(0);cin.tie(0);
   cin >> Case;
   while(Case --)
      TCS();
   std::cerr << (clock() - st) * 1.0 / CLOCKS_PER_SEC;
   ret 0;}