每次选不重合的第一次出现一定是最优解。
设定阈值 $B$。当 $|t_i|> B$ 时直接 KMP 匹配，时间复杂度 $O(\frac{n\sum|t_i|}{B})$。当 $|t_i|\le B$ 时，总共只有 $O(nB)$ 次出现，离线建 Trie 后处理即可。
取 $B=\sqrt{\sum |t_i|}$，时间复杂度为 $O(n\sqrt{\sum|t_i|})$。
QOJ.ac
QOJ
As we are currently experiencing an overwhelming number of web requests for fetching user submissions, we have temporarily disabled the full submissions list. You must now be logged in to view submissions.
Discussion #209 for Problem #11746. Consistent Occurrences
Type: Editorial
Status: Open
Posted by: jiangly
Posted at: 2025-12-13 00:13:41
Last updated: 2025-12-13 00:13:44
题解
Comments
No comments yet.