题目理解

我们有两个长度为 $n$ 的序列 $S$ 和 $T$，它们都由正整数构成。题目要求：

1. 将 $T$ 切成连续的三段（每段非空）
2. 将这三段重新排列（任意顺序）
3. 重新排列后的三段拼接起来等于 $S$

换句话说，我们要找到两个切分点 $i, j$（$1 \le i < j \le n-1$），使得：

• $T[1..i], T[i+1..j], T[j+1..n]$ 这三段
• 经过某种排列后等于 $S$

解题思路

核心观察

由于只有 3 段，排列只有 $3! = 6$ 种可能。我们可以枚举所有排列情况，但直接枚举切分点会达到 $O(n^2)$ 的复杂度，对于 $n \leq 10^6$ 是不可行的。

算法框架

代码采用了字符串哈希 + 回文自动机的优化方法：

1. 枚举排列：实际上只枚举了两种主要情况
2. 使用哈希：快速比较子串是否相等
3. 利用回文性质：通过Manacher算法优化查找

主要函数分析

1. checkBAC() 函数

这个函数检查排列 $(B, A, C)$ 的情况，即：

• 第一段取 $T$ 的中间段
• 第二段取 $T$ 的开头段
• 第三段取 $T$ 的结尾段

算法步骤：

• 预处理 $S$ 和 $T$ 的哈希值
• 预处理 KMP 的 next 数组用于快速匹配
• 遍历所有可能的切分位置，利用哈希 $O(1)$ 比较子串

bool checkBAC() {
    // 检查后缀是否完全匹配
    for (ok[n + 1] = 1, i = n; i; i--)
        ok[i] = ok[i + 1] && (a[i] == b[i]);
    
    // 预处理KMP和哈希
    prework(a, nxta, ha);
    prework(b, nxtb, hb);

    // 遍历所有位置
    for (i = j = k = 0; i <= n; i++) {
        // 更新KMP指针
        if (i) {
            while (j && a[j + 1] != b[i]) j = nxta[j];
            if (a[j + 1] == b[i]) j++;
            
            while (k && b[k + 1] != a[i]) k = nxtb[k];
            if (b[k + 1] == a[i]) k++;
        }

        if (!ok[i + 1]) continue;

        // 检查两种匹配情况
        if (j > 0 && ... && ask(ha, j + 1, i) == ask(hb, 1, i - j)) {
            // 找到解，记录三段位置
            add(i - j + 1, i);  // 中间段
            add(1, i - j);      // 开头段  
            add(i + 1, n);      // 结尾段
            return true;
        }
        // 另一种对称情况...
    }
    return false;
}

2. checkCBA() 函数

这个函数检查排列 $(C, B, A)$ 的情况，使用了**回文自动机（Manacher算法）**来优化查找。

算法思想：

• 将 $S$ 和反转的 $T$ 交错拼接：$a_1, b_n, a_2, b_{n-1}, ...$
• 在这个新串上运行Manacher算法找回文
• 利用回文性质快速确定可行的切分点

bool checkCBA() {
    // 构建交错序列
    for (i = 1; i <= n; i++)
        c[++m_val] = a[i], c[++m_val] = b[n - i + 1];
    
    // Manacher算法找最长回文
    for (r = p_val = 0, f[1] = 1, i = 2; i < len; i++) {
        for (f[i] = r > i ? min(r - i, f[p_val * 2 - i]) : 1; 
             s[i - f[i]] == s[i + f[i]]; f[i]++);
        if (i + f[i] > r)
            r = i + f[i], p_val = i;
    }
    
    // 利用回文信息寻找解
    // ...
}

3. 对称性处理

由于问题具有对称性，代码通过反转数组来检查更多情况：

// 原始情况
if (checkBAC()) return true;

// 反转后检查
reverse(a + 1, a + n + 1);
reverse(b + 1, b + n + 1);
if (checkBAC()) {
    fix();
    reverseans();  // 将解映射回原始坐标
    return true;
}

// 恢复原数组，检查第三种情况
reverse(a + 1, a + n + 1);
reverse(b + 1, b + n + 1);
if (checkCBA()) return true;

哈希技术

使用双哈希防止碰撞：

typedef unsigned long long ll;
const int BASE = 233;

// 预处理幂次
for (p[0] = i = 1; i <= n; i++)
    p[i] = p[i - 1] * BASE;

// 计算哈希
for (i = 1; i <= n; i++)
    g[i] = g[i - 1] * BASE + a[i];

// 查询子串哈希
inline ll ask(ll *f, int l, int r) {
    return f[r] - f[l - 1] * p[r - l + 1];
}

复杂度分析

• 哈希预处理：$O(n)$
• KMP预处理：$O(n)$
• Manacher算法：$O(n)$
• 主算法：每个测试用例 $O(n)$

总复杂度：$O(\sum n)$，可以处理 $n \leq 10^6$ 的数据规模。

样例分析

样例1

S: 2 1 1 1 1
T: 1 1 1 1 2

解：

• 切分 $T$ 为：[1..3] = 1 1 1, [4] = 1, [5] = 2
• 排列为：2 + 1 1 1 + 1 = 2 1 1 1 1 = $S$

样例3

S: 4 5 2 1 4
T: 5 4 2 1 4

解：

• 切分 $T$ 为：[2] = 4, [1] = 5, [3..5] = 2 1 4
• 排列为：4 + 5 + 2 1 4 = 4 5 2 1 4 = $S$

算法亮点

1. 哈希优化：$O(1)$ 比较任意子串
2. 对称性利用：通过反转减少枚举情况
3. 回文性质：利用Manacher算法进一步优化
4. 完备性：覆盖所有可能的排列情况

这个解法巧妙地结合了多种字符串算法，在保证正确性的同时达到了线性复杂度，能够处理大规模数据。