AT_abc434_f [ABC434F] Concat (2nd) 题解 / Z 函数学习笔记

zrl123456 · 2025-11-30 17:06:21 · 题解

:::::info[题目基本信息] 考察：Z 函数，字符串，贪心（个人认为中位紫）。
题目简介：
给定 n 个由小写英文字母构成的字符串 \{s_n\}，你可以选择一个 n 阶排列 \{p_n\}，取最终字符串为 res=s_{p_1}+s_{p_2}+\dots+s_{p_n}，其中 + 表示字符串拼接，求所有能得到的字典序非严格次小的最终字符串。
数据范围：

• 2\le n\le 3\times 10^5
• \forall i\in[1,n],|s_i|\ge 1
• \sum_{i=1}^n|s_i|\le 10^6

  ::::: 这是一道经典题目，我们更常见的是求字典序最小的字符串，所以我们先介绍怎么求最小。
  由于交换任意两项可以通过多次交换相邻两项得到，所以我们仅需论证交换相邻两项何时会变优即可，至于为何贪心交换一定最优会在后面论证。
  为书写方便令 s'_i=s_{p_i}，现在我们将 res=s'_1+s'_2+\dots+s'_p+s'_{p+1}+\dots+s'_n 交换 s_p 和 s_{p+1} 两项变成 res'=s'_1+s'_2+\dots+s'_{p+1}+s'_p+\dots+s'_n，那么 s_1 到 s_{p-1} 字典序相同，我们容易得到判定条件：若 a,b（现在 a 位于 b 前）交换后变优当且仅当 a+b>b+a。
  不妨将 a+b<b+a 记为 a\prec b。
  那么这个 a+b<b+a 的排序条件可排序吗？也就是说 \prec 是否具有传递性？
  :::::success[证明] 遇到这种东西我们的思路就是移项，但是现在我们是字符串运算我们不能移项，所以我们考虑将其替换。
  注意到 a+b 和 b+a 长度相同，所以我们可以把它们哈希成一个 26 进制数，设 a 的哈希为 A，b 的哈希为 B，那么 a+b<b+a 等价于 A\cdot 26^{|b|}+B<B\cdot 26^{|a|}+A，这时移项可以得到：

  \frac{A}{26^{|a|}-1}<\frac{B}{26^{|b|}-1}

  这个东西显然有传递性，证毕。
  ::::: 同时我们注意到，上面满足那坨东西的一定是最优的，至于其它的我们一定可以交换相邻两项，这时我们补上了贪心交换的正确性。
  那么这样你直接排序能通过 P1012，时间复杂度是 \mathcal{O}(n\max|s_i|\log n) 的，这个题就不太能过了。
  下文启用 1-base。
  我们注意到此时一次比较时间复杂度为 \Theta(|a|+|b|)，我们观察到我们至少将比较时间降至 \Theta(\min(|a|,|b|)) 才能通过，那么我们考虑优化。

• 当 |a|=|b| 时，|a|+|b| 与 \min(|a|,|b|) 同量级，可以直接比。

• 否则不妨钦定 |a|<|b|，分成三部分：

  • 先比较 a 和 b[1,|a|]（s[l,r] 表示 s_l 到 s_r 的字符拼接形成的字符串）的大小关系。
  • 再比较 b[1,|b|-|a|] 和 b[|a|+1,|b|] 的大小关系。
  • 最后比较 b[|b|-|a|+1,|b|] 和 a 的大小关系。

  容易发现中间一部分最耗时，考虑优化。注意到这是同一字符串内的操作，所以我们可以预处理，但是预处理大小关系是不现实的，我们可以考虑快速找到第一个不同的位置，所以我们可以计算 b 和 b 的每一个后缀的 LCP 长度，唉这不就是 Z 函数吗，直接算就行了。

:::::success[Z 函数介绍]{open} 下文切换 0-base。
设 z_i 表示 s 和 s[i,|s|-1] 的 LCP 长度，z_0 无讨论价值，不考虑在内。
我们考虑在计算 z_i 时充分利用 z_1 到 z_{i-1} 的所有值，据 z_i 的定义我们可以得到 s[0,z_i-1] 和 s[i,i+z_i-1] 相同，所以当 i\in[j,j+z_j-1] 时我们可以直接利用，由于我们是正序枚举所以 i>j 必然成立，我们只需要找最大的 j+z_j-1 然后利用即可。
具体而言，令 l 为上述的最大的 j+z_j-1 的 j，然后分讨：

• 若 i\le l+z_l-1，我们可以利用前面的 Z 函数。
  • 若 z_{i-l}<l+z_l-i，那么我们直接令 z_i\leftarrow z_{i-l}，且容易发现不会继续扩展答案。
  • 否则，令 z_i\leftarrow l+z_l-i，并暴力扩展。
• 否则初值为 0 直接扩展。
• 然后更新 l。

下文切换回 1-base。
好的根据上述我们求出了字典序最小字符串，那么怎么求次小呢？

• 如果存在一对字符串（排序后显然相邻）使得 a+b=b+a 那么实际上次小也是最小。
• 否则通过手玩我们断言：最终答案要么是： s'_1+s'_2+\dots+s'_{n-2}+s'_n+s'_{n-1}

  要么是：

  s'_1+s'_2+\dots+s'_{n-1}+s'_{n-2}+s'_n

  :::::success[证明] 多次交换和交换不相邻位置非次优可以通过反证证明。 设交换一个 i\in[1,n-3] 得到了 s'_1+s'_2+\dots+s_{i+1}+s_i+\dots+s_{n-1}+s_n，那么由于原串与最小串不等，那么我们只需要找到第一个不等位置即可，容易发现不等位置 $\displaystyle pos1\in[(\sum{a=1}^{i-1}	s_a	)+1,\sum_{a=1}^{i+1}	s_a	]，容易发现一定不比交换 n-1,n$ 优。 证毕。
  时间复杂度为 $\mathcal{O}(\sum	s_i	\log n)，空间复杂度为 \Theta(\sum	s_i	)$。

code
:::::warning[坑点] 哦题解说得对，我们可以通过 Z 函数优化时间复杂度，好的开写。
怎么这么多 s[x] 和 s[y]，太长了，改一下吧。

string a=s[x],b=s[y];

TLE。
:::::