专栏文章

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

zzrl123456
题解参与者 1已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@mimxilu9
此快照首次捕获于
2025/12/01 17:10
3 个月前
此快照最后确认于
2025/12/01 17:10
3 个月前
查看原文
题目基本信息
考察：Z 函数，字符串，贪心（个人认为中位紫）。
题目简介：
给定 nn 个由小写英文字母构成的字符串 {sn}\{s_n\}，你可以选择一个 nn 阶排列 {pn}\{p_n\}，取最终字符串为 res=sp1+sp2+⋯+spnres=s_{p_1}+s_{p_2}+\dots+s_{p_n}，其中 ++ 表示字符串拼接，求所有能得到的字典序非严格次小的最终字符串。
数据范围：
  • 2≤n≤3×1052\le n\le 3\times 10^5
  • ∀i∈[1,n],∣si∣≥1\forall i\in[1,n],|s_i|\ge 1
  • ∑i=1n∣si∣≤106\sum_{i=1}^n|s_i|\le 10^6
这是一道经典题目，我们更常见的是求字典序最小的字符串，所以我们先介绍怎么求最小。
由于交换任意两项可以通过多次交换相邻两项得到，所以我们仅需论证交换相邻两项何时会变优即可，至于为何贪心交换一定最优会在后面论证。
为书写方便令 si′=spis'_i=s_{p_i}，现在我们将 res=s1′+s2′+⋯+sp′+sp+1′+⋯+sn′res=s'_1+s'_2+\dots+s'_p+s'_{p+1}+\dots+s'_n 交换 sps_p 和 sp+1s_{p+1} 两项变成 res′=s1′+s2′+⋯+sp+1′+sp′+⋯+sn′res'=s'_1+s'_2+\dots+s'_{p+1}+s'_p+\dots+s'_n，那么 s1s_1 到 sp−1s_{p-1} 字典序相同，我们容易得到判定条件：若 a,ba,b（现在 aa 位于 bb 前）交换后变优当且仅当 a+b>b+aa+b>b+a。
不妨将 a+b<b+aa+b<b+a 记为 a≺ba\prec b。
那么这个 a+b<b+aa+b<b+a 的排序条件可排序吗？也就是说 ≺\prec 是否具有传递性？
证明
遇到这种东西我们的思路就是移项，但是现在我们是字符串运算我们不能移项，所以我们考虑将其替换。
注意到 a+ba+b 和 b+ab+a 长度相同，所以我们可以把它们哈希成一个 2626 进制数，设 aa 的哈希为 AA，bb 的哈希为 BB，那么 a+b<b+aa+b<b+a 等价于 A⋅26∣b∣+B<B⋅26∣a∣+AA\cdot 26^{|b|}+B<B\cdot 26^{|a|}+A，这时移项可以得到：
A26∣a∣−1<B26∣b∣−1\frac{A}{26^{|a|}-1}<\frac{B}{26^{|b|}-1} 这个东西显然有传递性，证毕。
同时我们注意到，上面满足那坨东西的一定是最优的，至于其它的我们一定可以交换相邻两项，这时我们补上了贪心交换的正确性。
那么这样你直接排序能通过 P1012，时间复杂度是 O(nmax⁡∣si∣log⁡n)\mathcal{O}(n\max|s_i|\log n) 的，这个题就不太能过了。
下文启用 1-base。
我们注意到此时一次比较时间复杂度为 Θ(∣a∣+∣b∣)\Theta(|a|+|b|)，我们观察到我们至少将比较时间降至 Θ(min⁡(∣a∣,∣b∣))\Theta(\min(|a|,|b|)) 才能通过，那么我们考虑优化。
  • 当 ∣a∣=∣b∣|a|=|b| 时，∣a∣+∣b∣|a|+|b| 与 min⁡(∣a∣,∣b∣)\min(|a|,|b|) 同量级，可以直接比。
  • 否则不妨钦定 ∣a∣<∣b∣|a|<|b|，分成三部分：
    • 先比较 aa 和 b[1,∣a∣]b[1,|a|]（s[l,r]s[l,r] 表示 sls_l 到 srs_r 的字符拼接形成的字符串）的大小关系。
    • 再比较 b[1,∣b∣−∣a∣]b[1,|b|-|a|] 和 b[∣a∣+1,∣b∣]b[|a|+1,|b|] 的大小关系。
    • 最后比较 b[∣b∣−∣a∣+1,∣b∣]b[|b|-|a|+1,|b|] 和 aa 的大小关系。
    容易发现中间一部分最耗时，考虑优化。注意到这是同一字符串内的操作，所以我们可以预处理，但是预处理大小关系是不现实的，我们可以考虑快速找到第一个不同的位置，所以我们可以计算 bb 和 bb 的每一个后缀的 LCP 长度，唉这不就是 Z 函数吗，直接算就行了。
Z 函数介绍
下文切换 0-base。
设 ziz_i 表示 ss 和 s[i,∣s∣−1]s[i,|s|-1] 的 LCP 长度，z0z_0 无讨论价值，不考虑在内。
我们考虑在计算 ziz_i 时充分利用 z1z_1 到 zi−1z_{i-1} 的所有值，据 ziz_i 的定义我们可以得到 s[0,zi−1]s[0,z_i-1] 和 s[i,i+zi−1]s[i,i+z_i-1] 相同，所以当 i∈[j,j+zj−1]i\in[j,j+z_j-1] 时我们可以直接利用，由于我们是正序枚举所以 i>ji>j 必然成立，我们只需要找最大的 j+zj−1j+z_j-1 然后利用即可。
具体而言，令 ll 为上述的最大的 j+zj−1j+z_j-1 的 jj，然后分讨：
  • 若 i≤l+zl−1i\le l+z_l-1，我们可以利用前面的 Z 函数。
    • 若 zi−l<l+zl−iz_{i-l}<l+z_l-i，那么我们直接令 zi←zi−lz_i\leftarrow z_{i-l}，且容易发现不会继续扩展答案。
    • 否则，令 zi←l+zl−iz_i\leftarrow l+z_l-i，并暴力扩展。
  • 否则初值为 00 直接扩展。
  • 然后更新 ll。
注意到每次扩展都会令 l+zll+z_l 增长，所以时间复杂度为 Θ(∣s∣)\Theta(|s|)。
下文切换回 1-base。
好的根据上述我们求出了字典序最小字符串，那么怎么求次小呢？
  • 如果存在一对字符串（排序后显然相邻）使得 a+b=b+aa+b=b+a 那么实际上次小也是最小。
  • 否则通过手玩我们断言：最终答案要么是： s1′+s2′+⋯+sn−2′+sn′+sn−1′s'_1+s'_2+\dots+s'_{n-2}+s'_n+s'_{n-1} 要么是： s1′+s2′+⋯+sn−1′+sn−2′+sn′s'_1+s'_2+\dots+s'_{n-1}+s'_{n-2}+s'_n
证明
多次交换和交换不相邻位置非次优可以通过反证证明。
设交换一个 i∈[1,n−3]i\in[1,n-3] 得到了 s1′+s2′+⋯+si+1+si+⋯+sn−1+sns'_1+s'_2+\dots+s_{i+1}+s_i+\dots+s_{n-1}+s_n，那么由于原串与最小串不等，那么我们只需要找到第一个不等位置即可，容易发现不等位置 pos1∈[(∑a=1i−1∣sa∣)+1,∑a=1i+1∣sa∣]\displaystyle pos_1\in[(\sum_{a=1}^{i-1}|s_a|)+1,\sum_{a=1}^{i+1}|s_a|]，容易发现一定不比交换 n−1,nn-1,n 优。
证毕。
时间复杂度为 O(∑∣si∣log⁡n)\mathcal{O}(\sum|s_i|\log n)，空间复杂度为 Θ(∑∣si∣)\Theta(\sum|s_i|)。
code
坑点
哦题解说得对，我们可以通过 Z 函数优化时间复杂度，好的开写。
怎么这么多 s[x] 和 s[y]，太长了，改一下吧。
CPP
string a=s[x],b=s[y];
TLE。

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...