题解

思路推导

设最优子序列为 $T=(T')^k$。由于 $k|T'|\le |S|\le80$，重复次数 $k$ 与循环节长度 $|T'|$ 不可能同时很大。

当 $k=2$ 时，把 $S$ 切成前后两段。循环节 $T'$ 必须同时是两段的子序列，因此固定切分后的最优长度就是两段最长公共子序列长度的两倍。枚举所有切分即可。

当 $k=3$ 时同理：把 $S$ 切成三段，计算三段的最长公共子序列。$k=4$ 无需单独处理，因为 $(T')^4$ 也可视为 $(T'T')^2$，已经包含在 $k=2$ 的情况中。

若 $k\ge5$，则 $|T'|\le16$。把 $S$ 连续分为五段，每段长度至多 $16$。五份 $T'$ 的子序列匹配区间两两按顺序排列，而四个分界点不可能切到每一份匹配区间，因此至少有一份 $T'$ 完全落在某一段内。于是，只需枚举五段的所有子序列作为循环节候选。

做法

枚举一个切分点，对两段做二维最长公共子序列动态规划，用其结果更新 $k=2$ 的答案。

枚举两个切分点，对三段做三维最长公共子序列动态规划，用其结果更新 $k=3$ 的答案。

把字符串均分为五个连续块。枚举每块的所有非空子序列 $P$，再从左到右贪心匹配 $P$：每完整匹配一次就把重复次数加一并重新匹配 $P$。贪心能得到 $P$ 作为循环节时可重复的最大次数，因此用“重复次数乘 $|P|$”更新答案。

三个部分取最大值即为最终答案。

对于第一个子任务，可直接枚举 $S$ 的所有子序列并检查其最小周期。对于第二个子任务，若只有一种字符出现至少两次，则任意好的子序列只能由这一种字符组成，答案就是它的出现次数；若没有这样的字符则答案为零。

正确性证明

二维和三维最长公共子序列分别完整枚举了 $k=2$ 与 $k=3$ 的所有可能切分，因此这两类候选无重无漏。所有 $k=4$ 的候选又属于 $k=2$。

对 $k\ge5$，上述分界点论证保证最优循环节 $T'$ 一定作为子序列完整出现在五块之一，因此枚举一定会访问 $T'$。固定候选循环节时，从左到右选择每个所需字符的最早位置不会损失后续空间，所以贪心得到的重复次数最大。

综上，算法既不会遗漏任何可能成为最优解的重复次数类型，也只用实际可在 $S$ 中匹配的重复串更新答案，故结果正确。

复杂度分析

二维部分总复杂度为 $O(n^3)$；三维部分的总复杂度为 $O(n^5)$，但所有切分下三段长度乘积的总和具有较小常数；枚举五块子序列的复杂度为 $O(5\cdot2^{\lceil n/5\rceil}n)$。空间复杂度为 $O(n^3)$。