题解 CF594E 【Cutting the Line】

部分~~几乎全部~~内容摘抄自 zzy 的解题报告，orz zzy。 # 题目来源 IOI2020 集训队作业中 AC 人数最少的一道，毒瘤字符串。 截至 2020 年 2 月 17 日的统计：  注：一共有 $70$ 个人，所有作业题平均 AC 数量在 $40$ 以上。 # 题目大意 给定一个长度为 $n$ 的字符串 $S$，你需要把它划分成至多 $k$ 段，也就是使得 $S=s_1s_2\dots s_k$，然后决定每一段翻转或者不翻转，最后再顺次拼接得到 $T$，求字典序最小的 $T$。 # 数据范围 $1\le |S|\le 5\times 10^6,1\le k\le S$ # 预知识 符号含义： - $s[l]$ 表示 $S$ 的第 $l$ 个字符。（下标从 $1$ 开始） - $S[l,r]$ 表示 $S$ 这个字符串中从第 $l$ 个字符到第 $r$ 个字符的子串。 - $S[l:]$ 表示 $S[l,n]$，即 $S$ 这个字符串从第 $l$ 个字符开始的后缀。 - $S[:l]$ 表示 $S[1,l]$，即 $S$ 这个字符串前 $l$ 个字符形成的前缀。 - $s+t$ 或 $st$ 表示 $s,t$ 这两个字符串顺次拼接。 - $s^k$ 表示 $k$ 个 $s$ 顺次拼接。 - $s^r$ 表示 $s$ 的反串。 ## 一、$\text{Lyndon}$ 分解 我们定义一个串是 $\text{Lyndon}$ 串，当且仅当这个串的最小后缀就是这个串本身。 该命题等价于这个串是它的所有循环表示中字典序最小的。 --- #### 引理 1：如果 $u$ 和 $v$ 都是 $\text{Lyndon}$ 串并且 $u<v$，则 $uv$ 也是 $\text{Lyndon}$ 串。 证明： ##### 1、若 $\operatorname{len}(u)\ge\operatorname{len}(v)$ 这时，$u$ 和 $v$ 这两个串在 $\operatorname{len}(v)$ 之前就出现了不同的字符，所以有 $v>uv$，又因为 $v$ 是 $\text{Lyndon}$ 串，所以 $v$ 的所有后缀都大于 $v$，所以 $uv$ 的所有后缀都大于 $uv$，故 $uv$ 是 $\text{Lyndon}$ 串。 ##### 2、若 $\operatorname{len}(u)<\operatorname{len}(v)$ 若 $u$ 不是 $v$ 的前缀，那么有 $v>uv$，得证。 若 $u$ 是 $v$ 的前缀，那么如果 $v<uv$，则必有 $v[\operatorname{len}(u)+1:]<v$（也就是各自去掉了前 $|u|$ 个字符），矛盾。 --- 我们定义一个串 $S$ 的 $\text{Lyndon}$ 分解为一个字符串序列 $A_1,A_2,\dots,A_m$，满足： - $S=A_1A_2\cdots A_m$。 - $\forall i \in [1,m]$，满足 $A_i$ 是 $\text{Lyndon}$ 串。 - $\forall i \in [1,m-1]$，满足 $A_i\ge A_{i+1}$。 可以证明这种划分存在且唯一。 ### 存在性证明 初始令 $m=|S|$ 并且 $A_i=S[i]$，然后每次不断找到 $A_i<A_{i+1}$ 并且合并为一个串。最后一定能使得所有的 $A_i\ge A_{i+1}$。 ### 唯一性证明 假设对于字符串 $S$ 存在两个不同的 $\text{Lyndon}$ 分解： $$S=A_1A_2\cdots A_iA_{i+1}A_{i+2}\cdots A_{m_1}$$ $$S=A_1A_2\cdots A_iA^\prime_{i+1}A^\prime_{i+2}\cdots A^\prime_{m_1}$$ 不妨设 $\operatorname{len}(A_{i+1})>\operatorname{len}(A^\prime_{i+1})$。 观察 $A_{i+1}$ 在第二种分解中的对应情况。假设 $A_{i+1}=A^\prime_{i+1}A^\prime_{i+2}\cdots A^\prime_{k}+(A^\prime_{k+1}[:l])$。 那么由 $\text{Lyndon}$ 串的性质可知： $$A_{i+1}<A^\prime_{k+1}[:l]\le A^\prime_{k+1}\le A^\prime_{i+1}<A_{i+1}$$ 矛盾。 --- #### 引理2：若字符串 $v$ 和字符 $c$ 满足 $vc$ 是某个 $\text{Lyndon}$ 串的前缀，则对于字符 $d>c$ 有 $vd$ 是 $\text{Lyndon}$ 串。 证明： 设该 $\text{Lyndon}$ 串为 $v+c+t$。 则 $\forall i \in [2,|v|],v[i:]+c+t>v+c+t$，也就是说 $v[i:]+c\ge v$。 所以 $v[i:]+d>v[i:]+c\ge v$。 同时因为 $c>v[1]$，我们有 $d>c>v[1]>v$。 故 $v+d$ 是一个 $\text{Lyndon}$ 串。 --- ### $\text{Duval}$ 算法 这个算法可以在 $O(n)$ 时间复杂度，$O(1)$ 空间复杂度内求出一个串的 $\text{Lyndon}$ 分解。 该算法中我们仅需维护三个变量 $i,j,k$。 维持一个循环不变式： - $s[:i-1]=s_1s_2\cdots s_g$ 是固定下来的分解，也就是 $\forall l\in[1,g],s_l$ 是 $\text{Lyndon}$ 串且 $s_l>s_{l+1}$。 - $s[i,k-1]=t^h+v(h>1)$ 是没有固定的分解，满足 $t$ 是 $\text{Lyndon}$ 串，且 $v$ 是 $t$ 的可为空的不等于 $t$ 的前缀，且有 $s_g>s[i,k-1]$ 如下图：  当前读入的字符是 $s[k]$，令 $j=k-|t|$。 分三种情况讨论： - 当 $s[k]=s[j]$ 时，直接 $k\leftarrow k+1,j\leftarrow j+1$，周期 $k-j$ 继续保持 - 当 $s[k]>s[j]$ 时，由**引理 2** 可知 $v+s[k]$ 是 $\text{Lyndon}$ 串，由于 $\text{Lyndon}$ 分解需要满足 $s_i\ge s_{i+1}$，所以不断向前合并，最终整个 $t^h+v+s[k]$ 形成了一个新的 $\text{Lyndon}$ 串。 - 当 $s[k]<s[j]$ 时，$t^h$ 的分解被固定下来，算法从 $v$ 的开头处重新开始。 复杂度分析：$i$ 只会单调往右移动，同时 $k$ 每次移动的距离不会超过 $i$ 移动的距离，所以时间复杂度是 $O(n)$ 的。 代码如下（刚贡献的[P6129](https://www.luogu.com.cn/problem/P6127)）： ```cpp #include<cstdio> #include<algorithm> #include<cstring> using namespace std; char s[5000005]; int n,ans; int main() { scanf("%s",s+1); n=(int)strlen(s+1); for(int i=1;i<=n;) { int j=i,k=i+1;//初始化 while(k<=n&&s[j]<=s[k]) { if(s[j]<s[k])j=i;//合并为一整个 else j++;//保持循环不变式 k++; } while(i<=j)//从v的开头继续 { ans^=i+k-j-1; i+=k-j; } } printf("%d\n",ans); return 0; } ``` ## 二、扩展 KMP / Z-algorithm 这个算法可以在 $O(n)$ 的时间复杂度内求出一个串的所有后缀和这个串的LCP，在思路上和 manacher 有想通之处。 我们设 $z_i$ 表示 $s[i:]$ 和 $s$ 的 LCP 长度。注意在这里要满足 $i\ge 2$。 我们设 $[i,i+z_i-1]$ 为第 $i$ 个位置的 Z-box。我们记录当前右端点最靠右的那个 Z-box 为 $[l,r]$。 假设现在要求出 $z_i$。分两种情况讨论： - 若 $i>r$，那么令 $l=r=i$，暴力向后匹配。 - 否则，令 $k=z_i-l+1$，则如果 $z_k< r-i+1$，就直接让 $z_i=z_k$，否则先让 $z_i=r-i+1$，然后暴力匹配。 由于 $r$ 只会单调往右，所以时间复杂度也是 $O(n)$。 再附一张图：  代码： ```cpp int l=0,r=0; for(int i=2;i<=n;i++) { if(i>r) { l=r=i; while(r<=n&&s[r-l+1]==s[r])r++; z[i]=r-l,r--; } else { int k=i-l; if(z[k]<r-i+1)z[i]=z[k]; else { l=i; while(r<=n&&s[r-l+1]==s[r])r++; z[i]=r-l,r--; } } } ``` # 解题过程 令 $n=|S|$。 ## Part 1：$k=n$ 当 $k=n$ 的时候，我们注意到不需要考虑分割数量的限制。 注意到，如果其中有一个子串没有翻转，那么我们可以把这个子串进一步分割成单个字符，并且每一个字符都翻转（因为单个字符所以是否翻转无影响），也就是说，一定存在一个最优解，满足划分出来的每一段都进行了翻转。 我们用 $S^r$ 表示 $S$ 的反串，则问题等价于每次从 $S^r$ 中截取一个后缀并且拼接在当前字符串之后，直到 $S^r$ 为空。 --- #### 引理 3：一个字符串的最小后缀在这个字符串中出现的位置不交 证明：设最小后缀为 $A$，如果 $A$ 出现的位置有交，则 $A$ 必定有一个前缀等于后缀，那么 $A$ 的那个后缀的字典序就要小于 $A$，我们就找到了一个更小的后缀，矛盾。 --- 我们先找到 $S^r$ 的最小后缀，假设它为 $A$，那么为了让最后得到的串字典序尽可能小，我们必然想使得 $T$ 的开头出现尽可能多的 $A$。 可以发现，我们当前操作把后缀 $A$ 拿出来一定不会让答案变劣。 至此，对于 $k=n$ 的情况，我们已经有了思路：只需要每次取 $S^r$ 的字典序最小的后缀，得到的 $T$ 就是字典序最小的。 考虑 $\text{Lyndon}$ 分解的性质。由于 $s_m$ 是 $\text{Lyndon}$ 串，并且对于任意 $i<m$ 有 $s_m\le s_i$，所以 $s_m$ 就是字典序最小的后缀。 做一遍 $\text{Lyndon}$ 分解，时间复杂度 $O(n)$。 ## Part 2: $k\neq n$ 当 $k$ 变小的时候，我们不能随心所欲地进行分割，需要尽可能节约操作次数。 注意到，某些操作是可以合并的： - 如果连续两次截取的字符串相同，那么可以合为一次。 - 如果连续两次截取的字符串都为回文串，那么可以合为一次。 第一条很简单，关于第二条，别忘了在原问题中我们是可以对字符串进行翻转的。 让 $T$ 的开头出现尽可能多的 $A$，这个原则没变。我们把 $S^r$ 中所有的 $A$ 提出来并把 $S^r$ 写成下面这种形式： $$S^r=s_0+c_1A+s_1+c_2A+\cdots+s_{m-1}+c_mA$$ 其中 $s_0,s_1,\dots,s_{m-1}$ 是字符串序列，其中 $s_1,s_2,\dots,s_{m-1}$ 不能为空串，$c_1,c_2,\dots,c_m$ 是正整数序列。 ### case 1：$k\ge 3$ 注意到，如果这个时候我们取的是 $c_mA$，那么至少可以使得开头出现 $c_m+\max_{i=1}^{m-1}c_i$ 个 $A$，而如果在别的位置分割，无论如何不可能出现这些个 $A$。 所以此时就是取最后的一段 $c_mA$。 但是我们很快找到了一组反例：$S^r=\text{efcdbbbaaa},k=3$。 此时，$A=\text{``a''},S=\text{``efcdbbb''}+3A$。 如果我们第一次把 $3A$ 分割出来了，那么问题变成了 $S=\text{``efcdbbb''},k=2$，最终得到的 $T$ 最优是 $\text{``aaabbbdcef''}$。 而如果我们第一次截取的是 $\text{``bbbaaa''}$ 并且将它翻转，那么可以得到 $T=\text{``aaabbbcdef''}$，显然后者才是最优解。 究其原因，我们发现此时 $\text{``aaa''}$ 和 $\text{``bbb''}$ 都是回文串，而两次都是回文串的话可以合并为一次。 由于一个串的最小后缀除非长度为 $1$ 否则不可能是回文（要不然直接拿最后一个字符当后缀就更优了），所以发生上面这种情况当且仅当 $A$ 和截取后的 $S^r$ 的最小后缀长度都是 $1$。特判这种情况。 在具体实现上，在 $\text{Lyndon}$ 分解的过程中，先把 $S^r$ 末尾所有相等的 $\text{Lyndon}$ 串（设它们是 $s_k,s_{k+1},\cdots,s_m$）合并并且将其添加到 $T$ 的末尾，然后如果 $s_m$ 和 $s_{k-1}$ 长度都是 $1$ 就不消耗步数，否则让 $k-1$。 ### case 2：$k\le 2$ $k=1$ 自然不需要处理，如果 $k=2$，那么我们可以枚举第一次分割出来的是哪个串，并且对分割出来的两端是否翻转进行分类讨论。 可以用诸如后缀自动机之类的算法实现 $O(1)$ 求任意两个子串的 LCP。 至此，我们已经有了一个时间复杂度为 $O(n)$ 的 **算法 $1$** 了： 首先特判 $k=1$，将 $S$ 翻转得到 $S^r$，对 $S^r$ 进行一次 $\text{Lyndon}$ 分解，并且将 $S$ 和 $S^r$ 拿出来建后缀自动机。 接下来不断重复如下过程： - 如果 $k\ge 3$，就截取末尾所有相等的 $\text{Lyndon}$ 串，如果 $s_m$ 和 $s_{k-1}$ 长度都是 $1$ 就不消耗步数，否则让 $k-1$。 - 如果 $k=2$，就暴力枚举断点，然后用后缀自动机实现 $O(1)$ 查询 LCP。 ## Part 3 上述做法当 $k=2$ 的时候太过暴力了，实现也不够优美。它并没有充分利用字符串的相关性质。我们尝试发掘性质优化算法。 再重复一遍当前的问题：你有一个 $S^r$，你需要先截取 $S^r$ 的一个后缀，选择翻转或者不翻转得到 $t_1$，然后选择把 $S^r$ 剩下的部分翻转或者不翻转得到 $t_2$，要求 $t_1+t_2$ 的字典序最小。 让我们进行分类讨论： ### case 1：两次都翻转 答案就是 $S$。注意这里的翻转是指对反串进行翻转。 ### case 2：两次都不翻转 相当于要求 $S^r$ 的最小循环表示。 最小循环表示可以用如下算法来求（如果会请跳过）： --- 首先令 $s=s+s$。 维护三个变量 $i,j,k$，表示 $s[i:]$ 和 $s[j:]$ 的前 $k$ 个字符相同。 接下来分情况： - $i=j$：令 $j+1$。 - $s[i+k]=s[j+k]$：令 $k+1$。 - $s[i+k]<s[j+k]$：此时对于任意一个 $x\in [j,j+k]$，一定都能在 $[i,i+k]$ 中找到一个对应的 $y$，使得 $s[y:]<s[x:]$，所以直接令 $j=j+k+1$，同时令 $k=0$。 - $s[i+k]>s[j+k]$：同理，令 $i=i+k+1,k=0$。 如果 $i,j$ 其中有一个大于 $n$ 或者 $k\ge n$，就返回 $i,j$ 中较小的一个。 --- 时间复杂度 $O(n)$，因为 $i+j+k$ 是单调上升的。 ### case 3：第一次翻转，第二次不翻转 从后到前枚举断点 $i$，假设当前的最优解是 $j$：  相当于要求 $\left(S^r[i,j-1]\right)^r+S[:i-1]$ 和 $S^r$ 的字典序。 可以转化为两次询问： - $(S^r[i,j-1])^r$ 和 $S^r$ 的 LCP - $S^r[j-i+1,j-1]$ 和 $S^r$ 的 LCP 由于所有的询问都是关于整个 $S^r$ 的，因此可以使用扩展 KMP 算法来求解。具体地，令 $S'=S^r+S$，则我们只需要求出这个串的所有后缀和这个串的 LCP。 时间复杂度 $O(n)$。 ### case 4：第一次不翻转，第二次翻转 重点来了。 我们重新设 $S^r$ 的 $\text{Lyndon}$ 分解结果如下： $$S^r=A_1^{k_1}A_2^{k_2}\cdots A_m^{k_m}$$ $$S^r=B_1B_2\cdots B_m$$ 其中满足 $A_1>A_2>\cdots>A_m,B_i=A_i^{k_i}$。 为了方便，我们再设 $SB_i=B_iB_{i+1}\cdots B_{m}$。 --- #### 定理 1：最终答案一定满足存在一个 $i$，使得 $t_1=SB_i$。 也就是说我们一定会在 $B$ 的分界线上进行截取。 证明：若最优答案不在 $B$ 的分界线上，分情况讨论： - 若截取的位置位于 $A$ 的分界线上，那么分界线左右一定都是一样的 $\text{Lyndon}$ 串 $A_i$，那么 $t_1=SB_{i}$ 和 $t_1=SB_{i+1}$ 这两种方案中一定有一种更优。 - 若截取的位置不在 $A$ 的分界线上，那么一定在某一个 $A_i$ 的内部。由于 $A_i$ 是 $\text{Lyndon}$ 串，所以把分界线向前移动到 $A_i$ 的分界线上一定会更优。 --- #### 引理 4：若 $s_1$ 是 $\text{Lyndon}$ 串并且满足 $s_1>s_2\ge s_3$，则 $s_1>s_2+s_2\ge s_2+s_3$。 证明：分两种情况讨论。 - 若 $s_2$ 不是 $s_1$ 的前缀，则 $s_1$ 和 $s_2$ 在比较的时候直接产生不同。 - 若 $s_2$ 是 $s_1$ 的前缀，则 $s_3\le s_2<s_1<s_1[|s_2|:]$，故成立。 --- #### 定理 2：$SB_i>SB_{i+1}$。 证明：取 $SB_i$ 的第一个 $\text{Lyndon}$ 串 $A_i$，再将 $SB_{i+1}$ 写成 $\text{Lyndon}$ 分解的形式，由**引理 4** 可以得出 $SB_i>A_i>SB_{i+1}$。 --- 由**定理 2** 可知，除非 $SB_{i+1}$ 是 $SB_i$ 的前缀，否则 $t_1=SB_{i+1}$ 一定会被 $t_1=SB_i$ 更优。 我们取最后一个满足 $SB_{p}$ 不是 $SB_{p-1}$ 的前缀的 $p$，那么由刚刚的讨论可知 $t_1=SB_p$ 一定优于前面的任意一个 $SB_i$，也就是说如果最优答案中 $t_1=SB_i$，则一定满足 $i\ge p$。 --- #### 定理 3：若 $SB_{i+1}$ 是 $SB_i$ 的前缀，则一定满足 $\operatorname{len}(SB_{i+1})\le \dfrac 12\operatorname{len}(SB_i)$ 证明：如下图：  我们发现 $SB_i$ 前面出现了两个 $t$，而 $t=B_i=A_i^{k_i}$，这显然矛盾。 --- **定理 3** 告诉我们，$SB_p,SB_{p+1},\dots,SB_m$ 这些串一定满足后一个长度不大于前一个的 $1\over 2$，所以至多只会有 $O(\log n)$ 个。 枚举 $O(\log n)$ 个断点，然后二分+哈希比较大小，这一部分的时间复杂度可以做到 $O(\log^2n)$。 ### 继续分析性质 首先假设 $SB_i$ 比 $SB_{i-1}$ 更优秀。 再来一张大图：  直线表示平移，曲线表示翻转。 看下面两个，由于 $SB_i$ 比 $SB_{i-1}$ 优秀，所以 $X^r<Y$。 再看上面两个，由于 $X^r<Y$，所以我们就可以直接得出 $SB_i$ 比 $SB_{i-2}$ 优秀。 换句话说，我们只需要找到最大的 $q$，满足 $SB_q$ 比 $SB_{q-1}$ 优秀，那么令 $t_1=SB_q$ 就是答案。 由于一次比较是 $O(\operatorname{len}(SB_i))$ 的，所以我们从 $SB_m$ 往前一个串一个串暴力比较，时间复杂度就是 $O(n)$，~~因此暴力算几项就完事了！!1~~ 至此，我们就得到一个非常优美的**算法 2**了： **步骤 1**：特判 $k=1$，并且将 $S$ 翻转得到 $S^r$，对 $S^r$ 进行 $\text{Lyndon}$ 分解。 **步骤 2**：如果 $k\ge 3$，则每次截取最后一段 $B_m$，如果 $A_m$ 和 $S_{m-1}$ 长度都是 $1$ 则不消耗步数。 **步骤 3**：如果 $k=2$，则进行分类讨论： - 两次均翻转：答案即为 $S$。 - 两次均不翻转：答案即为 $S^r$ 的最小表示。 - 第一次翻转，第二次不翻转：用 KMP 算法实现查询 LCP。 - 第一次不翻转，第二次翻转：暴力比较求出最后一个 $SB_q$ 比 $SB_{q-1}$ 优秀，则 $t_1=SB_q$ 就是答案。 时间复杂度 $O(n)$ ~~甚至 $O(n\log n)$。~~ # 代码 ```cpp #include<cstdio> #include<algorithm> #include<cstring> using namespace std; char s[10000005],t[5000005],t1[5000005],t2[5000005],t3[5000005],t4[5000005]; int n,k,m,nowl,z[10000005],A[5000005],l[5000005]; void extend(char*s,int l)//在t串之后新加入s[:l-1] { for(int i=0;i<l;i++)t[++nowl]=s[i]; } void solve1(int n)//两段都翻转，直接就是原串 { for(int i=1;i<=n;i++)t1[i]=s[n-i+1]; } void solve2(int n)//两段都不翻转，最小表示法 { for(int i=n+1;i<=2*n;i++)s[i]=s[i-n]; int i=1,j=2,k=0; while(i<=n&&j<=n&&k<n) { if(s[i+k]==s[j+k])k++; else if(s[i+k]<s[j+k])j+=k+1,k=0; else i+=k+1,k=0; if(i==j)j++; } for(int x=0;x<n;x++)t2[x+1]=s[min(i,j)+x]; } void solve3(int n)//第一段翻转第二段不翻转，扩展 KMP { for(int i=n+1;i<=2*n;i++)s[i]=s[n-(i-n)+1]; n*=2; z[1]=n; int l=1,r=1; for(int i=2;i<=n;i++) { if(r<i) { l=r=i; while(r<=n&&s[r]==s[r-l+1])r++; z[i]=r-l; r--; } else { if(z[i-l+1]<r-i+1)z[i]=z[i-l+1]; else { l=i; while(r<=n&&s[r]==s[r-l+1])r++; z[i]=r-l; r--; } } }//以上为扩展KMP算法 n/=2; int j=n+1; for(int i=n;i>=1;i--) { int l=i,r=j-1; l=n-l+1,r=n-r+1; int len=z[r+n]; if(len<l-r+1) { if(s[len+1]>s[j-len-1])j=i; } else { len=j-i; l=len+1,r=j-1; if(s[z[l]+1]<s[l+z[l]])j=i; } } int tot=0; for(int i=n;i>=j;i--)t3[++tot]=s[i]; for(int i=1;i<j;i++)t3[++tot]=s[i]; } void solve4(int n)//第一次不翻转，第二次翻转，暴力比较 { int p=m; while((A[p+1]-A[p])*2<=(A[p]-A[p-1])) { bool flag=0; for(int i=A[p]-1;i>=A[p-1];i--) { if(s[i]<s[n-i+A[p-1]]) { flag=1; break; } if(s[i]>s[n-i+A[p-1]])break; } if(flag)break; p--; } p=A[p]; int tot=0; for(int i=p;i<=n;i++)t4[++tot]=s[i]; for(int i=p-1;i>=1;i--)t4[++tot]=s[i]; } void update(char*t1,char*t2,int n)//取字典序最小 { for(int i=1;i<=n;i++) { if(t1[i]<t2[i])return; if(t2[i]<t1[i])break; } for(int i=1;i<=n;i++)t1[i]=t2[i]; } void solve(int n) { solve1(n); solve2(n); solve3(n); solve4(n); update(t1,t2,n); update(t1,t3,n); update(t1,t4,n); extend(t1+1,n); } int main() { scanf("%s",s+1); n=(int)strlen(s+1); scanf("%d",&k); for(int i=1;i*2<=n;i++)swap(s[i],s[n-i+1]);//取反串 if(k==1)//特判k=1 { for(int i=1;i<=n;i++)t[i]=s[n-i+1]; for(int i=1;i<=n;i++) { if(s[i]<t[i]) { printf("%s\n",s+1); return 0; } if(s[i]>t[i]) { printf("%s\n",t+1); return 0; } } printf("%s\n",s+1); return 0; } for(int i=1;i<=n;)//Lyndon分解 { int j=i,k=i+1; while(s[j]<=s[k]) { if(s[j]<s[k])j=i; else j++; k++; } A[++m]=i; l[m]=k-j; while(i<=j)i+=k-j; } A[m+1]=n+1; while(m&&k>=3)//当k>=3时 { extend(s+A[m],A[m+1]-A[m]); if(l[m]!=1||l[m-1]!=1)k--; m--; } if(!m) { printf("%s\n",t+1); return 0; } solve(A[m+1]-1);//当k=2时 printf("%s\n",t+1); return 0; } ``` # 总结 本道题涉及到了后缀自动机，$\text{Lyndon}$ 分解，扩展 KMP，最小表示法等等多种字符串冷门算法，综合考察了选手对前沿字符串算法的掌握能力、调试代码能力和肝脏承受能力，难度适中，覆盖知识点广，题目又着切合实际的背景，解法比较自然。给出题人点赞！