好神。
考虑到我们二分答案。
那么我们要做的是这样一个事情：

判定s[c,d - l]在s[a,b]是否以子串形式出现过。

那这是一个\(SAM\)的很套路的题目：
我们考虑到我们维护每个endpos集合的出现的子串，这个我们在\(link\)树上做线段树合并即可。
我们从表示\(s[1,b]\)的SAM节点倍增往上跳找到表示\(s[a,b]\)的点就行了。
那我们只要看\(len\)就可以做了。

代码鸽，存了个计划表，如果我NOIP没退役就回来写这个计划表。

[HEOI2016/TJOI2016]字符串