题目链接：「SDOI2017」文本校正
难度：NOI/NOI+/CTSC\FCOLORBOX{#2C3E50}{#E9ECEF}{\COLOR{#2C3E50}NOI/NOI+/CTSC}NOI/NOI+/CTSC
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
题目大意
给定两个长度均为 n 的序列 S,TS,TS,T。
将 TTT 划分为连续、非空的三段 A,B,CA,B,CA,B,C，满足 T=A+B+CT=A+B+CT=A+B+C。我们可以对这三个块做任意排列，把重排后的块拼接得到 SSS。
判断是否存在这样的划分与重排；若存在输出 YES，并输出拼接顺序对应的三段在 T 中的区间；无解输出 NO。
> 限制：3≤n≤1063\le n \le 10^63≤n≤106，∑n≤106\sum n \le 10^6∑n≤106，字符集大小 m≤106m\le 10^6m≤106。
> 注意：块内部字符顺序不能改变，只能交换块之间的先后顺序。
排列分析
A,B,CA,B,CA,B,C 三个块一共有 6 种全排列：
1. A+B+CA+B+CA+B+C
2. A+C+BA+C+BA+C+B
3. B+A+CB+A+CB+A+C
4. B+C+AB+C+AB+C+A
5. C+A+BC+A+BC+A+B
6. C+B+AC+B+AC+B+A
暴力枚举分割点 i,ji,ji,j，再枚举 6 种排列是 O(n2)O(n^2)O(n2)，无法通过大数据。我们把 6 种情况归约成 4 类子问题，分别用字符串算法处理。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
整体解题思路
1. Case1：S=A+B+CS=A+B+CS=A+B+C，块顺序不变，即 S=TS=TS=T。使用 KMPKMPKMP 匹配。
2. Case2：S=C+B+AS=C+B+AS=C+B+A，块整体逆序。构造拼接串，使用 ManacherManacherManacher 回文算法。
3. Case3：S=A+C+B, S=B+C+AS=A+C+B,\ S=B+C+AS=A+C+B, S=B+C+A：第一个块来自 T 的某一段，剩下两个块拼接接在后面。使用 Z‑AlgorithmZ‑AlgorithmZ‑Algorithm + 线段树。
4. Case4：S=B+A+C, S=C+A+BS=B+A+C,\ S=C+A+BS=B+A+C, S=C+A+B：将 S,TS,TS,T 整体反转，转化为 Case3，复用同一套 Z 函数代码。
只要其中任意一类找到可行解，就输出答案；全部无解输出 NO。
> > 注意！由于本题SPJ问题，只用输出YES或NO即可，不需要输出 TTT 的 3 个子串。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
算法复杂度分析
1. KMPKMPKMP：O(n)O(n)O(n)
2. Manacher：O(n)O(n)O(n)
3. Z 函数：O(n)O(n)O(n)；线段树建树、查询：O(nlogn)O(n\log n)O(nlogn)
总复杂度 ∑nlogn\sum n\log n∑nlogn，可以处理 n=106n=10^6n=106。
数组开 2×1062\times10^62×106，内存满足 512MB 限制。
易错点（AI易错，所以AI过不了这一题，剩下的I DON'T KNOW）
1. 三段划分必须全部非空，不能出现空区间；
2. 反转序列后坐标变换容易出错，out函数是重灾区；
3. 下标全部从 1 开始，注意边界；
4. 多组数据，注意数组的重置；
5. 字符串算法模板不要把 S,TS,TS,T 搞反。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
CODE:
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
如果你对我的 代码/题解 有疑问 或 我的 代码/题解 有错可以在此评论。
