Description：

给你很多 $01$ 串，和一个模板串，如果可以把模板串划分成很多部分，一些部分能和某个模板串匹配长度超过 $k$ ，并且匹配的总长度超过 $90\%$ ，那么划分合法，求最长的 $k$ 。

$1\leqslant l\leqslant 1000000$

Solution：

先二分一个值 $k$ ，然后判断是否存在一种划分每一个长度都超过 $k$ 并且匹配的总长度 $\geqslant90\%$ ，那么可以暴力 $DP$ ： $$ f[i]=\max(f[i-1],f[j]+(i-j)[s[j+1,i]合法]) $$ 那现在我们的关键问题就在于如何快速判断一段是否是合法的。那么我们就可以建出广义后缀自动机，然后用模板串在上面跑，求出以每一个位置结束的最长匹配 $maxlen[i]$ ，那么转移方程就变成了： $$ f[i]=\max(f[i-1],i+f[j]-j(i-maxlen[i]\leqslant j\leqslant i-1)) $$ 由于 $i-maxlen[i]$ 单调不降，所以用单调队列维护滑动窗口最大值即可。

但是还有一个问题，要求转移的时候 $i-j\geqslant k$ 怎么办？其实只要不每次都把 $i$ 加进去，而是每次把 $i-k$ 加入队列就行了。

Code：