问题

给定文本串$SS$和模式串$TT$，求$SS$的一个最长子串，使得其为$TT$重复其某个子区间的结果。

题解

KMP

对$SS$正向做一次$TT$的匹配，记录$SS$每个前缀$pr{e}_{i}pre\_i$尾部能匹配到的$TT$最长的前缀，记做$f_{i}f\_i$。

对$SS$逆向做一次$TT$的匹配，记录$SS$每个后缀$su{f}_{i}suf\_i$前部能匹配到的$TT$最长的后缀，记做$g_{i}g\_i$。

如果$f_i+g_{i+1}>\mathrm{\mid }T\mathrm{\mid }f\_i\; +\; g\_\{i\; +\; 1\}\; >\; |T|$，则可以更新答案。

时间复杂度$O(\mathrm{\mid }S\mathrm{\mid }+\mathrm{\mid }T\mathrm{\mid })O(|S|\; +\; |T|)$

吐槽

其实这题代码很短，出题人和验题人都认为是Medium Easy或者Medium难度，但很奇妙的是内榜和外榜都一直没人做这题，校内吹了一堆F的气球没发出去。感觉榜有些歪？

虽然说题解是KMP，但实际过题方法众多。我的某个队友写了哈希+二分，另一个因为没带SAM板子干脆就没写，真是绝活。