1. 问题理解 我们有一个字符串 $t$，它是接收到的消息。系统原本要连续发送两条完全相同的消息 $s$，但在传输过程中可能发生一种合并错误：

第一条消息完整发送：$s$

发送第二条消息时，它的开头与第一条消息的结尾发生重叠（重叠部分字符必须完全相同）

重叠长度记为 $L$，必须满足 $0 < L < |s|$（既不能完全不重叠，也不能完全重叠）

因此实际发送的第二个消息是 $s[L..|s|-1]$（即去掉前 $L$ 个字符）

最终接收到的字符串 $t$ 为：

$t=s+s[L..∣s∣−1]$

注意：

如果 $L = 0$，则 $t = s + s$，这是简单的拼接，不视为错误。

如果 $L = |s|$，则 $t = s$，这是完全重叠，也不视为错误。

题目要求：给定 $t$，判断是否存在某个 $s$ 和某个 $L$（$1 \le L \le |s|-1$）使得上述等式成立。若存在，输出任意一个 $s$；否则输出 "NO"。

2. 数学建模 设：

$n = |t|$

$m = |s|$

$L$ 为重叠长度，满足 $1 \le L \le m-1$

根据合并规则：

$t=s+s[L..m−1]$

等式右边的长度： $|s| + (m - L) = m + m - L = 2m - L$ 因此：

$n=2m−L$

由此可得：

$L=2m−n$

由于 $L$ 必须满足 $1 \le L \le m-1$，我们得到关于 $m$ 的不等式：

$\begin{cases} 2m - n \geq 1 & \Rightarrow m \geq \frac{n+1}{2} \\ 2m - n \leq m - 1 & \Rightarrow m \leq n - 1 \end{cases}$ ​

同时 $m$ 是整数，所以： $\left\lceil \frac{n+1}{2} \right\rceil \leq m \leq n - 1$

另外，$L$ 必须为正整数，所以 $2m - n \ge 1$ 自然包含在 $m \ge \frac{n+1}{2}$ 中。

3. 算法思路 因为 $n \le 100$，我们可以枚举所有可能的 $m$（原消息长度）。对于每个 $m$：

计算 $L = 2m - n$。

检查 $1 \le L \le m-1$（由枚举范围保证，但可显式判断）。

取候选 $s = t[0..m-1]$（前 $m$ 个字符）。

验证两个条件：

后缀匹配：$t[m..n-1]$ 必须等于 $s[L..m-1]$ 因为 $t =$ s$+$s[L..m-1]$，所以$t$从第$m$个字符开始应该是$s$去掉前$L$ 个字符。

重叠一致性：$s[0..L-1]$ 必须等于 $s[m-L..m-1]$ 因为重叠部分既是第一个 $s$ 的结尾，也是第二个 $s$ 的开头，它们必须相同。

如果两个条件都满足，则找到了合法的 $s$，输出并结束。

若所有 $m$ 都不满足，输出 "NO"。

4. 详细推导与正确性证明 必要性： 如果存在 $s$ 和 $L$ 使得 $t = s + s[L..m-1]$，那么显然 $m$ 一定在 $\lceil (n+1)/2 \rceil$ 到 $n-1$ 之间（因为 $L \ge 1$ 且 $L \le m-1$）。此时：

$t$ 的前 $m$ 个字符就是 $s$，所以 $s = t[0..m-1]$。

$t$ 的后 $n-m$ 个字符就是 $s[L..m-1]$，所以 $t[m..n-1] = s[L..m-1]$。

重叠部分 $s[0..L-1]$ 和 $s[m-L..m-1]$ 都是长度为 $L$ 的字符串，且它们相等（因为它们都等于第二个消息的前缀，也等于第一个消息的后缀）。 因此，我们枚举到正确的 $m$ 时一定会通过验证。

充分性： 如果我们枚举某个 $m$，并验证了上述两个条件成立，那么定义 $s = t[0..m-1]$，$L = 2m-n$。 由条件 $t[m..n-1] = s[L..m-1]$ 可得 $t = s + s[L..m-1]$。 由条件 $s[0..L-1] = s[m-L..m-1]$ 可知重叠部分一致，且 $1 \le L \le m-1$（因为 $m$ 的范围保证了 $L \ge 1$，且验证时也检查了 $L < m$）。因此 $t$ 确实是由错误产生的。

所以算法是正确的。

$5$. 复杂度分析 枚举 $m$：最多 $n$ 次（实际上从 $\lceil (n+1)/2 \rceil$ 到 $n-1$，约 $n/2$ 次）。

每次验证需要比较子串：$t.substr(m)$ 和 $s.substr(L)$ 长度均为 $n-m$，$s.substr(0,L)$ 和 $s.substr(m-L,L)$ 长度均为 $L$，每次比较最坏 $O(n)$。

总时间复杂度 $O(n^2)$，$n \le 100$ 时非常快。

空间复杂度 $O(n)$，用于存储字符串和子串（子串操作通常返回新字符串，但也可以使用指针比较优化，这里 $n$ 很小，直接使用即可）。