解题思路

思路

设目标字符串为 $s$，长度为 $n$。覆盖位置 $1$ 的那次放置必然从位置 $1$ 开始，因此它写出的字符串是 $s$ 的某个前缀，或者是该前缀的反向串。若某个模板可行，它的反向模板也可行，所以对每个长度 $L$，只需检查候选模板 $s[1\ldots L]$。

把所有能够放置候选模板或其反向模板的区间起点排序，并在末尾加入哨兵 $n+1$。这些长度均为 $L$ 的区间能够覆盖整个字符串，当且仅当相邻两个起点之差都不超过 $L$。

做法

令 $f_i$ 表示从位置 $i$ 开始与整个字符串前缀相同的最长长度。它可以由 Z 函数在线性时间内求出。于是长度为 $L$ 的正向模板可以从 $i$ 开始放置，当且仅当 $f_i\ge L$。

再令 $g_i$ 表示以位置 $i$ 结束、从右向左读取时与字符串前缀相同的最长长度。对 $s+\#+\operatorname{rev}(s)$ 求 Z 函数即可得到全部 $g_i$。长度为 $L$ 的反向模板可以在 $i$ 结束，当且仅当 $g_i\ge L$；它的区间起点是 $i-L+1$。

前三个子任务

当 $n\le500$ 时，可以对每个 $L$、每个起点和每个字符直接比较，复杂度为 $O(n^3)$。

预处理 $f$ 和 $g$ 后，每次匹配可以在常数时间内判断。对每个 $L$ 扫描所有位置并检查最大起点间距，复杂度降为 $O(n^2)$，可通过 $n\le5000$。

对于 $n\le100000$，按 $L$ 递增维护满足 $f_i\ge L$ 的正向起点集合和满足 $g_i\ge L$ 的反向终点集合。检查某个 $L$ 时，从尚未覆盖部分的最左位置出发，每次选择所有可衔接区间中右端点最远的一个。三个连续被选择的区间中，第一个和第三个必不相交，否则第二个不会被最远延伸贪心选中，所以长度 $L$ 至多选择 $2n/L$ 个区间。全部长度的选择次数为 $O(n\log n)$，集合查询再带来一个对数，复杂度为 $O(n\log^2 n)$。

满分算法

对当前仍有效的正向起点集合 $A$ 和反向终点集合 $B$，定义 $t$ 为：若把 $A$ 中的每个位置视为一个向右延伸、长度为 $t$ 的区间，把 $B$ 中的每个位置视为一个向左延伸、长度为 $t$ 的区间，这些区间覆盖整个字符串所需的最小长度。

当候选长度为 $L$ 时，集合中恰好保留 $f_i\ge L$ 或 $g_i\ge L$ 的放置位置。此时 $L$ 可行当且仅当 $L\ge t$。

随着 $L$ 增大，放置位置只会被删除，所以 $t$ 不会减小。删除一个区间之前，所有区间在当前 $t$ 下已经覆盖完整。删除之后，只有该区间原来所在的位置可能产生新缺口。把所有区间统一写成起点：正向区间起点为 $i$，反向区间起点为 $i-t+1$。找到被删起点两侧仍存在的最近起点，若二者距离不超过 $t$，缺口仍被覆盖；否则令 $t$ 增加 $1$ 并重新检查。区间随 $t$ 增大只会扩张，因此第一次重新满足条件时得到的仍是最小值。

正向起点的前驱和后继可以直接在 $A$ 中查询。若要查询不超过 $x$ 的最大反向起点，只需在 $B$ 中查询不超过 $x+t-1$ 的最大终点；后继查询同理。实现中每个位置只删除一次，并用只删集合的前驱、后继并查结构完成查询。变量 $t$ 最多从 $1$ 增长到 $n$，因此总查询次数为 $O(n)$。

正确性证明

首先，对固定长度 $L$，覆盖首字符的放置决定了候选模板必为长度为 $L$ 的前缀或其反向串；两者成对出现，所以检查该前缀不会漏解。

其次，Z 函数给出的 $f_i$ 和 $g_i$ 分别精确刻画正向与反向模板的全部合法放置。长度相同的区间覆盖整段字符串，当且仅当排序后的相邻起点距离不超过区间长度，因此集合判定与题意等价。

在动态过程中，删除放置位置不会降低最小覆盖长度。删除一个区间前覆盖成立，删除后除相邻前驱与后继之间外，其余相邻关系都没有改变，所以只检查这一处缺口充分且必要。若当前 $t$ 不足，增大 $t$ 会扩张所有区间，不会破坏已有覆盖；逐一增加直到缺口闭合，得到删除后新的最小覆盖长度。由归纳可知，每个 $L$ 处理完删除后，维护的 $t$ 都是当前合法放置集合的最小覆盖长度，故输出条件 $L\ge t$ 恰好等价于长度 $L$ 可行。

复杂度分析

两次 Z 函数计算为 $O(n)$。每个正向起点和反向终点各删除一次，$t$ 总共增加至多 $n-1$ 次，只删集合操作的均摊复杂度为反阿克曼函数量级。总时间复杂度为 $O(n\alpha(n))$，空间复杂度为 $O(n)$。