题目理解

我们有一个字符串 $S$，先复制一次得到 $T = S + S$，然后在 $T$ 中插入一个字符得到 $U$。
现在给出 $U$，需要还原出 $S$。

---

关键观察

设 $n = |U|$，$m = |S|$。
由于 $U$ 是由长度为 $2m$ 的 $T$ 插入一个字符得到的： [ n = 2m + 1 \quad\Rightarrow\quad m = \frac{n-1}{2} ] 因此 $n$ 必须是奇数，否则直接输出 NOT POSSIBLE。

---

问题转化

在 $U$ 中删除插入的那个字符后，剩下的字符串应该是 $S + S$。
插入位置有两种可能情况：

1. 插入位置在前半段：插入字符在第一个 $S$ 中
2. 插入位置在后半段：插入字符在第二个 $S$ 中

---

算法思路

1. 检查两种情况

情况1：插入字符在第一个 $S$ 中

• 取 $U$ 的后 $m$ 个字符作为完整的第二个 $S$（记为 a1）
• 取 $U$ 的前 $m+1$ 个字符作为可能包含插入字符的第一个 $S$（记为 b1）
• 检查 a1 是否是 b1 删除一个字符后的子序列

情况2：插入字符在第二个 $S$ 中

• 取 $U$ 的前 $m$ 个字符作为完整的第一个 $S$（记为 a2）
• 取 $U$ 的后 $m+1$ 个字符作为可能包含插入字符的第二个 $S$（记为 b2）
• 检查 a2 是否是 b2 删除一个字符后的子序列

2. 子序列检查函数

ll ch(string a, string b) {
    ll i = 0, j = 0;
    while (i < a.size() && j < b.size()) {
        if (a[i] == b[j]) {
            i++;
            j++;
        } else {
            j++;
        }
    }
    return (i == a.size()) ? j : -1;
}

该函数检查 a 是否是 b 的子序列，如果是则返回匹配结束位置。

3. 结果判断

• 如果两种情况都不满足：NOT POSSIBLE
• 如果两种情况都满足且得到的 $S$ 相同：输出 $S$
• 如果两种情况都满足但得到的 $S$ 不同：NOT UNIQUE
• 只有一种情况满足：输出对应的 $S$

---

代码步骤解析

1. 基本检查

if (n % 2 == 0) {
    cout << "NOT POSSIBLE";
    return 0;
}
ll m = (n - 1) / 2;

2. 检查情况1（插入字符在第一个S）

string a1 = s.substr(m + 1, m);  // 第二个完整的S
string b1 = s.substr(0, m + 1);  // 第一个S（可能多一个字符）
ll pos1 = ch(a1, b1);            // 检查a1是否是b1的子序列
if (pos1 != -1) {
    ch1 = true;
    s1 = a1;  // 候选S
}

3. 检查情况2（插入字符在第二个S）

string a2 = s.substr(0, m);      // 第一个完整的S  
string b2 = s.substr(m, m + 1);  // 第二个S（可能多一个字符）
ll pos2 = ch(a2, b2);            // 检查a2是否是b2的子序列
if (pos2 != -1) {
    ch2 = true;
    s2 = a2;  // 候选S
}

4. 输出结果

if (!ch1 && !ch2) {
    cout << "NOT POSSIBLE";
} else if (ch1 && ch2) {
    if (s1 == s2) {
        cout << s1;
    } else {
        cout << "NOT UNIQUE";
    }
} else if (ch1) {
    cout << s1;
} else {
    cout << s2;
}

---

复杂度分析

• 时间复杂度：$O(n)$，每个情况只需要线性扫描一次
• 空间复杂度：$O(n)$，存储子字符串

---

示例验证

样例1

输入: 7
      ABXCABC
情况1: a1 = "ABC", b1 = "ABXC" → 匹配成功，S = "ABC"
情况2: a2 = "ABX", b2 = "CABC" → 匹配失败
输出: ABC

样例2

输入: 6
      ABCDEF
n为偶数 → NOT POSSIBLE

样例3

输入: 9
      ABABABABA
情况1和情况2都匹配成功，但得到不同的S → NOT UNIQUE

---

算法标签

• 字符串处理
• 子序列匹配
• 情况分析

---

总结

本题通过分析插入字符的两种可能位置，将问题转化为子序列匹配问题，从而在线性时间内解决问题。关键思路是利用 $S+S$ 的结构特性，分别检查插入字符在前半段和后半段的情况。