题目重述 给定一个字符串 $t$，判断是否存在一个字符串 $s$ 和一个正整数 $L$（$1 \le L < |s|$），使得 $t$ 由两个 $s$ 重叠 $L$ 个字符拼接而成，即 $t=s+s[L:]$ 其中 $s[L:]$ 表示 $s$ 去掉前 $L$ 个字符的后缀。 例如，$s = \text{"abrakadabra"}$，$L=4$ 时，$t = \text{"abrakadabrakadabra"}$。

要求：若存在，输出任意一个可能的 $s$；否则输出 "NO"。 数据范围：$|t| \le 4\times 10^5$。

数学建模 设 $|s| = m$，$|t| = n$。由拼接方式知： $n=m+(m−L)=2m−L$ 因此重叠长度 $L = 2m - n$。

题目要求 $1 \le L < m$，即 $1≤2m−n<m$ 解不等式：

左边 $2m - n \ge 1 ;\Rightarrow; m \ge \frac{n+1}{2}$

右边 $2m - n < m ;\Rightarrow; m < n$

由于 $m$ 是整数，所以 $m$ 的取值范围为：

$\lfloor n/2 \rfloor + 1 \leq m \leq n-1$

换言之，我们只需枚举 $m$ 在这个区间内的每个整数，令 $L = 2m - n$，然后验证以下两个条件：

后缀条件：$t[m..n-1]$ 等于 $t[L..m-1]$ （因为 $t$ 的后半部分应该是 $s[L:]$，而 $s[L:]$ 恰好是 $t$ 的 $[L, m-1]$ 段）

前缀条件：$t[0..L-1]$ 等于 $t[m-L..m-1]$ （因为 $s$ 的前 $L$ 个字符与后 $L$ 个字符相同——它们就是重叠部分）

若存在某个 $m$ 同时满足这两个条件，则 $s = t[0..m-1]$ 即为答案。

关键观察 如果直接对每个 $m$ 比较子串，最坏情况需要 $O(n^2)$，不可接受。

我们需要一种能在 $O(1)$ 时间内判断任意两个子串是否相等的方法。

常用的工具有：字符串哈希、Z 函数、前缀函数（KMP）。这里选用简单高效的哈希法。

算法设计（哈希法）

1. 预处理哈希 选择一个大质数模数 $P$（例如 $10^9+7$）或使用自然溢出（$2^{64}$）。定义基数 $B$（例如 $91138233$ 或 $131$）。 对于字符串 $t$（下标从 $0$ 开始），计算前缀哈希数组 $h$ 和幂数组 $p$：

$h[0]=0$

$h[i+1]=(h[i]⋅B+(t[i]−'a'+1))modP$

$p[0]=1$

$p[i+1]=p[i]⋅BmodP$

则子串 $t[l..r]$（$0 \le l \le r < n$）的哈希值为：

$hash(l,r)=(h[r+1]−h[l]⋅p[r−l+1])modP$ 若使用自然溢出（unsigned long long），则自动模 $2^{64}$，无需取模操作。

2. 枚举 $m$ 从 $m = \lfloor n/2 \rfloor + 1$ 到 $m = n-1$，依次检查：

计算 $L = 2m - n$（此时 $1 \le L < m$ 自动成立）

检查 $\text{hash}(m, n-1) \stackrel{?}{=} \text{hash}(L, m-1)$

检查 $\text{hash}(0, L-1) \stackrel{?}{=} \text{hash}(m-L, m-1)$

如果两个条件都满足，则输出 $s = t[0..m-1]$，结束程序。

若循环结束未找到，输出 "NO"。

边界情况处理 当 $n \le 2$ 时，$m$ 的取值范围为空（因为 $\lfloor n/2 \rfloor + 1 \ge n$），直接输出 "NO"。例如 $n=1$ 或 $n=2$ 不可能构成错误。

注意题目明确：完全重叠（$L=0$）或简单拼接（$L=m$）不算错误，我们的枚举范围自然排除了这些情况。

字符串中可能包含相同字符，哈希能够正确处理。

复杂度分析 预处理哈希：$O(n)$

枚举 $m$：最多 $O(n)$ 次

每次判断：$O(1)$

总时间复杂度：$O(n)$

空间复杂度：$O(n)$（存储哈希数组和幂数组）

对于 $n \le 4\times10^5$，完全可行。 必要性： 若存在 $s$ 和 $L$ 使得 $t = s + s[L:]$，设 $m = |s|$，则 $n = 2m - L$，故 $L = 2m - n$。由 $1 \le L < m$ 可得 $m$ 在 $\lfloor n/2 \rfloor + 1$ 到 $n-1$ 之间。

因为 $t[m..n-1] = s[L:] = t[L..m-1]$，所以条件1成立。

又因为 $s$ 的前 $L$ 个字符与后 $L$ 个字符相同（即重叠部分），所以 $t[0..L-1] = s[0..L-1] = s[m-L..m-1] = t[m-L..m-1]$，条件2成立。 因此算法一定会找到这样的 $m$。

充分性： 若对于某个 $m$ 满足上述两个条件，令 $s = t[0..m-1]$，$L = 2m - n$。条件1说明 $t[m..n-1] = s[L:]$，条件2说明 $s[0..L-1] = s[m-L..m-1]$。那么 $t = s + s[L:]$，且 $L = 2m-n$ 满足 $1 \le L < m$（由 $m$ 的范围保证），因此 $s$ 是一个合法解。

综上，算法正确。