题解

思路

把字符串的所有后缀按字典序排列。长度为 $L$ 的某个子串至少出现 $m$ 次，当且仅当后缀数组中存在连续 $m$ 个后缀，它们两两公共前缀至少为 $L$。这等价于该窗口内相邻后缀最长公共前缀的最小值至少为 $L$。

做法

先构造后缀数组以及相邻后缀的最长公共前缀数组。对答案长度二分。

检查固定长度 $L$ 时，扫描最长公共前缀数组，把连续不小于 $L$ 的区间合并；若一个区间覆盖至少 $m$ 个后缀，则长度 $L$ 可行。所有可行区间中后缀起点的最大值，就是该长度下最靠右的出现位置。

二分得到最大可行长度后再检查一次，输出该长度和最靠右位置。若长度为零则输出 none。当 $m=1$ 时整串本身就是唯一最长答案，起点为零。

正确性证明

后缀数组中，所有以同一长度为 $L$ 的字符串开头的后缀必然构成连续区间。连续 $m$ 个后缀拥有长度至少为 $L$ 的公共前缀，当且仅当它们之间的所有相邻最长公共前缀均不小于 $L$。因此检查过程找到区间，恰好等价于存在出现至少 $m$ 次的长度 $L$ 子串。

在每个可行区间取最大的后缀起点，再对所有区间取最大值，得到所有最长候选中最靠右的出现位置。可行性关于 $L$ 单调，二分得到的最大可行长度正是题目所求最长长度。

复杂度分析

倍增法构造后缀数组的时间复杂度为 $O(n\log n)$，最长公共前缀数组和每次检查为 $O(n)$，二分检查总计 $O(n\log n)$；空间复杂度为 $O(n)$。