题解

思路

把 $s$ 无限重复得到周期字符串。若 $t$ 在某个模 $|s|$ 的起点出现，就可以尝试在偏移 $|t|$ 后继续接上另一个 $t$。这些起点构成一个每点至多一条出边的函数图；出现环表示可以无限连接，否则最长路径长度就是答案。

做法

子任务一：直接枚举重复次数

有限答案不会超过 $|s|$：若连续放置超过 $|s|$ 个 $t$，相邻两次放置的起点模 $|s|$ 必有重复，从而形成可以无限重复的周期。

因此可以依次构造 $t^i$，并把 $s$ 重复到足以覆盖所有模 $|s|$ 起点及目标长度，再直接查找 $t^i$ 是否出现。若 $i=|s|+1$ 仍可出现，答案为 $-1$；否则最后一个可出现的 $i$ 即为答案。

子任务二：逐起点比较与函数图

枚举 $p=0,1,\ldots,|s|-1$，逐字符比较 $t$ 与从循环字符串 $s$ 的位置 $p$ 开始的长度 $|t|$ 片段，标记哪些起点可以放置一个 $t$。

对每个合法起点 $p$，若 $q=(p+|t|)\bmod |s|$ 也合法，就连边 $p\to q$。若函数图存在环，沿环可以放置任意多个 $t$，答案为 $-1$；否则在无环图上求最长路径的节点数。

满分算法

逐起点比较最坏需要 $O(|s||t|)$。为了线性标记合法起点，只需取循环字符串 $s$ 的前 $|s|+|t|-1$ 个字符，并用 KMP 在其中查找模式串 $t$。这样每个模 $|s|$ 的起点对应的长度 $|t|$ 片段都恰好被检查一次。

得到合法起点后仍建立同一函数图。可用访问状态判环，并在路径回退时计算最长链；实现时使用显式数组和路径，避免递归深度达到 $5\times 10^5$。

复杂度

设 $n=|s|,m=|t|$。直接枚举层只用于 $n,m\le 10$。中等算法时间复杂度为 $O(nm)$，空间复杂度为 $O(n)$。

满分算法的时间复杂度为 $O(n+m)$，空间复杂度为 $O(n+m)$。

正确性说明

从合法起点 $p$ 放置一个 $t$ 后，下一个 $t$ 必须从 $(p+m)\bmod n$ 开始，因此任意连续的 $t$ 恰好对应函数图中的一条路径。反之，图中每经过一个合法节点，就能在循环字符串中继续放置一个完整的 $t$，所以任意路径都对应题目中的一个可行重复次数。

若图中存在环，可以沿环无限行走，故任意大的重复次数都可行，答案为 $-1$。若图无环，所有路径有限，最长路径的节点数就是能够连续放置的最多 $t$ 数量。

KMP 扫描的循环前缀覆盖了每个模 $n$ 起点及其后 $m$ 个字符，因此它标记的合法起点集合与逐起点定义完全一致。由此满分算法输出正确。