题目链接：「SDOI2017」文本校正

难度：$\fcolorbox{#2c3e50}{#e9ecef}{\color{#2c3e50}NOI/NOI+/CTSC}$

---

题目大意

给定两个长度均为 n 的序列 $S,T$。
将 $T$ 划分为连续、非空的三段 $A,B,C$，满足 $T=A+B+C$。我们可以对这三个块做任意排列，把重排后的块拼接得到 $S$。
判断是否存在这样的划分与重排；若存在输出 YES，并输出拼接顺序对应的三段在 T 中的区间；无解输出 NO。

限制：$3\le n \le 10^6$，$\sum n \le 10^6$，字符集大小 $m\le 10^6$。
注意：块内部字符顺序不能改变，只能交换块之间的先后顺序。

排列分析

$A,B,C$ 三个块一共有 6 种全排列：

1. $A+B+C$
2. $A+C+B$
3. $B+A+C$
4. $B+C+A$
5. $C+A+B$
6. $C+B+A$

暴力枚举分割点 $i,j$，再枚举 6 种排列是 $O(n^2)$，无法通过大数据。我们把 6 种情况归约成 4 类子问题，分别用字符串算法处理。

---

整体解题思路

1. Case1：$S=A+B+C$，块顺序不变，即 $S=T$。使用 $KMP$ 匹配。
2. Case2：$S=C+B+A$，块整体逆序。构造拼接串，使用 $Manacher$ 回文算法。
3. Case3：$S=A+C+B,\ S=B+C+A$：第一个块来自 T 的某一段，剩下两个块拼接接在后面。使用 $Z‑Algorithm$ + 线段树。
4. Case4：$S=B+A+C,\ S=C+A+B$：将 $S,T$ 整体反转，转化为 Case3，复用同一套 Z 函数代码。

只要其中任意一类找到可行解，就输出答案；全部无解输出 NO。

注意！由于本题SPJ问题，只用输出YES或NO即可，不需要输出 $T$ 的 3 个子串。

---

算法复杂度分析

1. $KMP$：$O(n)$
2. Manacher：$O(n)$
3. Z 函数：$O(n)$；线段树建树、查询：$O(n\log n)$

总复杂度 $\sum n\log n$，可以处理 $n=10^6$。
数组开 $2\times10^6$，内存满足 512MB 限制。

易错点（AI易错，所以AI过不了这一题，剩下的I don't know）

1. 三段划分必须全部非空，不能出现空区间；
2. 反转序列后坐标变换容易出错，out函数是重灾区；
3. 下标全部从 1 开始，注意边界；
4. 多组数据，注意数组的重置；
5. 字符串算法模板不要把 $S,T$ 搞反。

---

Code:

#include <bits/stdc++.h>
const int QWQ = 2e6 + 5;
using namespace std;
inline int read() {
    int x = 0, f = 1;
    char ch = getchar();

    for (; ch < '0' || ch > '9'; ch = getchar())
        if (ch == '-')
            f = -1;

    for (; ch >= '0' && ch <= '9'; ch = getchar())
        x = (x << 1) + (x << 3) + (ch ^ 48);

    return x * f;
}
int T, n, m, a[QWQ], b[QWQ];
void out(int al, int ar, int bl, int br, int cl, int cr, int f) {
    if (f) {
        swap(al, ar), al = n - al + 1, ar = n - ar + 1;
        swap(bl, br), bl = n - bl + 1, br = n - br + 1;
        swap(cl, cr), cl = n - cl + 1, cr = n - cr + 1;
        swap(al, cl), swap(ar, cr);
    }

    printf("YES\n");
}
namespace sol1 {
int t[QWQ], kmp[QWQ];
inline bool work() {
    for (int i = 1; i <= n; i++)
        t[i] = t[i + n] = b[i];

    for (int i = 2, j = 0; i <= n; i++) {
        for (; j && a[j + 1] != a[i]; j = kmp[j]);

        j += a[j + 1] == a[i], kmp[i] = j;
    }

    for (int i = 1, j = 0; i <= 2 * n; i++) {
        for (; j && a[j + 1] != t[i]; j = kmp[j]);

        j += a[j + 1] == t[i];

        if (j == n) {
            if (i == n)
                out(1, 1, 2, n - 1, n, n, 0);
            else if (i == 2 * n - 1)
                out(n, n, 1, 1, 2, n - 1, 0);
            else
                out(i - n + 1, i - n + 1, i - n + 2, n, 1, i - n, 0);

            return 1;
        }
    }

    return 0;
}
}
namespace sol2 {
int oz[QWQ], z1[QWQ], z2[QWQ], mx[QWQ * 2];
#define mid (l+r>>1)
#define rs (k<<1|1)
#define ls (k<<1)
inline int gmx(int x, int y) {
    return z1[x + 1] > z1[y + 1] ? x : y;
}
void make(int k, int l, int r) {
    if (l == r)
        return mx[k] = l, void();

    make(ls, l, mid), make(rs, mid + 1, r);
    mx[k] = gmx(mx[ls], mx[rs]);
}
int ask(int k, int l, int r, int ll, int rr) {
    if (ll > rr || ll < 1)
        return n + 1;

    if (ll <= l && rr >= r)
        return mx[k];

    int rx = n + 1;

    if (ll <= mid)
        rx = gmx(rx, ask(ls, l, mid, ll, rr));

    if (mid < rr)
        rx = gmx(rx, ask(rs, mid + 1, r, ll, rr));

    return rx;
}
inline void getz(int *z, int *oz, int *s, int *t) {
    fill(z, z + n + 3, 0);
    int l = 0, r = 0;

    for (int i = 1 + (z == oz); i <= n; i++) {
        if (i <= r)
            z[i] = min(r - i + 1, oz[i - l + 1]);

        for (; i + z[i] <= n && s[z[i] + 1] == t[i + z[i]]; z[i]++);

        if (i + z[i] - 1 > r)
            l = i, r = i + z[i] - 1;
    }
}
inline bool work(bool f) {
    if (f)
        reverse(a + 1, a + n + 1), reverse(b + 1, b + n + 1);

    getz(oz, oz, a, a), getz(z1, oz, a, b);
    getz(oz, oz, b, b), getz(z2, oz, b, a);
    // z1 : t->s ; z2 : s->t
    int p = 0;

    for (; p < n && a[n - p] == b[n - p]; p++);

    make(1, 1, n);
    int ok = 0;

    for (int i = 1; i <= n; i++) {
        int j = ask(1, 1, n, n - p - i, z2[i + 1]);

        if (j > n || z1[j + 1] < i)
            continue;

        out(j + 1, j + i, 1, j, i + j + 1, n, f);
        ok = 1;
        break;
    }

    if (f)
        reverse(a + 1, a + n + 1), reverse(b + 1, b + n + 1);

    return ok;
}
#undef mid
}
namespace sol3 {
int s[QWQ], d[QWQ];
inline bool cheak(int l, int r) {
    if (l > r)
        return 0;

    l = 2 * l - 1, r = 2 * r;
    return (l + r >> 1) + d[l + r >> 1] >= r;
}
inline bool work() {
    for (int i = 1; i <= n; i++) {
        s[2 * i - 1] = b[i], s[2 * i] = a[n - i + 1];
        d[2 * i - 1] = d[2 * i] = 0;
    }

    int mid = 0, r = 0;

    for (int i = 1; i <= 2 * n; i++) {
        if (i <= r)
            d[i] = min(r - i, d[2 * mid - i]);

        for (; i - d[i] >= 1 && i + d[i] + 1 <= 2 * n && s[i - d[i]] == s[i + d[i] + 1]; d[i]++);

        if (i + d[i] >= r)
            mid = i, r = i + d[i];
    }

    bool ok = 0;

    for (int i = n, l = n + 1, r = n; i > 1; i--) {
        if (cheak(i, n))
            l = i;

        r = min(r + 1, n);

        for (; r >= i && !cheak(i, r); r--);

        if (cheak(1, i - 1)) {
            if (i <= r && cheak(r + 1, n)) {
                out(r + 1, n, i, r, 1, i - 1, 0);
                ok = 1;
                break;
            } else if (l <= n && cheak(i, l - 1)) {
                out(l, n, i, l - 1, 1, i - 1, 0);
                ok = 1;
                break;
            }
        }
    }

    return ok;
}
}
signed main() {
    for (T = read(); T--;) {
        n = read(), m = read();
        bool is = 0;

        for (int i = 1; i <= n; i++)
            a[i] = read();

        for (int i = 1; i <= n; i++)
            b[i] = read();

        is |= sol1::work();

        if (is)
            goto end;

        is |= sol3::work();

        if (is)
            goto end;

        is |= sol2::work(0);

        if (is)
            goto end;

        is |= sol2::work(1);
end:
        ;

        if (!is)
            puts("NO");
    }

    return 0;
}

---

如果你对我的 代码/题解 有疑问 或 我的 代码/题解 有错可以在此评论。