被\(SAM\)和\(dp\)爆切就很难受
首先我们发现这个\(L\)显然有单调性，考虑二分
设 \(dp_i\) 表示匹配到第 \(i\) 位的最大匹配长度,然后处理 \(len_i\) 表示第 \(i\) 位能匹配到的最长子串
然后可以设计状态转移方程
首先很显然的 \(dp_i=dp_{i-1}\)
然后考虑其他转移 \(dp_i=\min\limits_{i-len_i \le j\le i-mid}dp_j+i-j\)
这个 \(dp\) 是 \(O(n^2)\) 的，考虑优化
发现可选区间右端点单调，且每个 \(dp\) 之间的优劣不会改变,可以用单调队列优化
复杂度\(O(\sum|T|log|T|)\)