题目 C. Saraga 详细题解

问题重述

给定两个字符串 $S$ 和 $T$，要求构造一个最短的字符串 $Z$，使得存在至少两种不同的方式将 $Z$ 分割成两个非空子串 $A$ 和 $B$（即 $Z = A + B$），其中 $A$ 是 $S$ 的前缀，$B$ 是 $T$ 的后缀。若不存在则输出 $-1$。

关键转化

对于任意一种分割方式，设分割点位于第 $k$ 个字符之后，即 $A = Z[1..k]$ 是 $S$ 的前缀，$B = Z[k+1..|Z|]$ 是 $T$ 的后缀。令 $P = Z[1..k-1]$（可能为空？但要求 $A$ 非空，所以 $k \ge 1$；$B$ 非空，所以 $k < |Z|$；而 $P$ 可以为空，但后续需要 $P$ 非空？实际上我们后面会要求 $P$ 非空，但这里先保留）。再令 $Q = Z[k]$（单个字符），$R = Z[k+1..|Z|]$，则：

• $A = P + Q$ 是 $S$ 的前缀，
• $B = R$ 是 $T$ 的后缀，且 $Q + R$ 也是 $T$ 的后缀（因为 $Q+R = Z[k..|Z|]$ 是 $B$ 加上前面一个字符，不一定是后缀？注意，$Q+R$ 实际上是 $Z$ 从 $k$ 开始的后缀，而 $B$ 是从 $k+1$ 开始，所以 $Q+R$ 不一定是 $T$ 的后缀。但我们可以换一种方式：另一种常见的分解是 $Z = P + (Q+R)$，其中 $Q+R$ 是 $T$ 的后缀。所以实际上，对于一个分割点 $k$，我们可以定义三元组 $(P, Q, R)$ 满足：
  • $Z = P + Q + R$，
  • $P+Q$ 是 $S$ 的前缀，
  • $Q+R$ 是 $T$ 的后缀，
  • $|Q| = 1$（因为 $Q$ 恰好是分割点处的单个字符）。

因此每一种分割方式都对应一个单字符 $Q$。

化简到 $|Q|=1$

题目要求至少两种不同的分割方式，即存在两个不同的单字符位置 $c_1$ 和 $c_2$（可能相同字符但位置不同），使得相应的条件成立。可以证明（见标程推导），任何有趣的缩写都可以通过不断将 $Q$ 的最后一个字符移到 $R$ 前面，最终得到一个 $|Q|=1$ 的表示，且该表示仍然具有至少两种分割方式。因此，我们只需要考虑 $|Q|=1$ 的情况。

构造方法

对于任意一个字符 $c$，假设存在一个 $S$ 的前缀 $Pc$（长度 $\ge 2$）以 $c$ 结尾，并且存在一个 $T$ 的后缀 $cR$（长度 $\ge 2$）以 $c$ 开头。那么构造

其中 $Pc$ 是 $S$ 的前缀（长度为 $i$），$cR$ 是 $T$ 的后缀（长度为 $j$），则 $R$ 的长度为 $j-1$。于是 $|Z| = i + j - 1$。

这个 $Z$ 自动具有两种不同的分割方式：

1. 分割点在 $Pc$ 的末尾：$A = Pc$（$S$ 的前缀），$B = R$（$T$ 的后缀，因为 $cR$ 是后缀，去掉第一个字符 $c$ 后 $R$ 仍是后缀）。
2. 分割点在 $Pc$ 去掉最后一个字符后的位置：设 $Pc = P' + c$，则 $P'$ 是 $S$ 的前缀（长度 $i-1 \ge 1$），且 $cR$ 是 $T$ 的后缀，于是 $A = P'$，$B = cR$，两者非空且满足条件。

因此，只要存在这样的 $c$，就能构造出一个有趣的缩写。为了得到最短的 $Z$，我们只需对每个 $c$，取 $S$ 中最短的以 $c$ 结尾的前缀（即最小的 $i \ge 2$ 使得 $S[i]=c$），以及 $T$ 中最短的以 $c$ 开头的后缀（即最小的 $j \ge 2$ 使得 $T$ 的倒数第 $j$ 个字符为 $c$），然后计算长度 $i+j-1$，取所有 $c$ 中的最小值即可。

算法步骤

1. 初始化两个数组 $\text{pref}[26]$ 和 $\text{suf}[26]$ 为无穷大。
2. 遍历 $S$（下标从 $1$ 开始），对于 $i = 2$ 到 $|S|$，令 $c = S[i]$，更新 $\text{pref}[c] = \min(\text{pref}[c], i)$。
3. 遍历 $T$，对于 $j = |T|-1$ 到 $1$（即从倒数第二个字符向前），令 $c = T[j]$，后缀长度 $len = |T| - j + 1$（$\ge 2$），更新 $\text{suf}[c] = \min(\text{suf}[c], len)$。
4. 枚举 $c = 0$ 到 $25$，若 $\text{pref}[c]$ 和 $\text{suf}[c]$ 均非无穷，则候选长度 $L = \text{pref}[c] + \text{suf}[c] - 1$，记录最小 $L$ 及对应的 $c$。
5. 若无任何候选，输出 $-1$；否则，输出 $S[1..\text{pref}[c]] + T[|T|-\text{suf}[c]+2 .. |T|]$（即 $S$ 的前 $\text{pref}[c]$ 个字符拼接 $T$ 的最后 $\text{suf}[c]-1$ 个字符）。

复杂度分析

• 预处理 $O(|S|+|T|)$。
• 枚举 $26$ 个字母 $O(1)$。
• 总时间复杂度 $O(|S|+|T|)$，满足 $|S|,|T| \le 2\times 10^5$ 的要求。

边界情况

• 如果 $|S|=1$ 或 $|T|=1$，则无法找到长度 $\ge 2$ 的前缀或后缀，输出 $-1$。
• 注意字符串下标从 $0$ 开始时的实现细节。

参考代码（C++）

#include <bits/stdc++.h>
using namespace std;

int main() {
    string S, T;
    cin >> S >> T;
    int n = S.size(), m = T.size();
    const int INF = 1e9;
    vector<int> pref(26, INF), suf(26, INF);
    // 最短前缀（长度>=2）以某字母结尾
    for (int i = 1; i < n; ++i) { // i是索引，对应长度i+1
        int c = S[i] - 'a';
        pref[c] = min(pref[c], i+1); // 长度 = i+1
    }
    // 最短后缀（长度>=2）以某字母开头
    for (int j = m-2; j >= 0; --j) {
        int c = T[j] - 'a';
        int len = m - j; // 从j到末尾的长度
        suf[c] = min(suf[c], len);
    }
    int best_len = INF;
    char best_c = -1;
    for (int c = 0; c < 26; ++c) {
        if (pref[c] != INF && suf[c] != INF) {
            int len = pref[c] + suf[c] - 1;
            if (len < best_len) {
                best_len = len;
                best_c = c;
            }
        }
    }
    if (best_c == -1) {
        cout << -1 << endl;
    } else {
        string ans = S.substr(0, pref[best_c]) + T.substr(m - (suf[best_c] - 1));
        cout << ans << endl;
    }
    return 0;
}