题解：P15650 [省选联考 2026] 摩卡串 / string

Mr_Terminator · 2026-03-10 15:27:32 · 题解

::::info[以下是场上对答案长度上界的极唐诗脑补证明，如果不想看可以跳过。]

• 定理 1：首先我们需要确认的一点是：答案如果存在，则最短长度 \le 2m。

  记答案串是 t。我们将所有小于 s 的区间中所有位置作出一个标记。

  • 引理 1：如果 r_0\le r,t_{[l,r]}<s，则 t_{[l,r_0]}<s。

  证明：显然。

  • 引理 2：对于被标记的一个下标 i，存在 l 使得 t_{[l,i]}<s。

  证明：根据标记的定义，存在 l,r 使得 l\le i\le r,t_{[l,r]}<s。由于 i\le r，故此时 t_{[l,i]}<s。由此也可以知道被标记的下标数量不超过 m。

  • 引理 3：若存在满足条件的 t，则存在未被标记的下标数量 \le m 的 t。

  证明：由于 m>0，故若存在 t，则 s\not=\texttt{0}。若 |s|=1，即 s=\texttt{1}，则在 m=1 时构造 t=\texttt{10}，否则构造 t=\texttt{0}+(m-1)\times\texttt{1}，|t|\le 2m。

  若 |s|>1，则考虑调整法。假设你有一个未被标记的下标数量 >m 的 t，则总能找到一个前面没有字符或者未被标记的位置，删除之。

::::

总之就是答案若存在，则长度 \le 2m。

记答案为 t。记 C_l=\operatorname{LCP}(t_{[l,|t|]},s),R_l=l+C_l-1。

• 若 C_l=n，则 l 作为左端点贡献了 n-1 个 <s 的区间，并且使得 s 是 t 的子串。

• 若 C_l<n,s_{C_l+1}=0，则 l 作为左端点贡献了 C_l 个区间。

• 若 C_l<n,s_{C_l+1}=1，则 l 作为左端点贡献了 |t|-l+1=C_l+(|t|-R_l) 个区间。