蒟蒻刚学了 SA，有点思路，问问各位 dalao 对不对。

给定一个长度为 $n$ 的字符串 $s$，$q$ 次询问 $\operatorname{lcp}(s_{l1,r1},s_{l2,r2}),l1\le l2$。

先跑 SA，求出 height，用 ST 表维护 height 的最小值。$\operatorname{lcp}(s_{l1,n},s_{l2,n})=query(rk_{l1}+1,rk_{l2})$。

加上长度限制，$\operatorname{lcp}(s_{l1,r1},s_{l2,r2})=\min\{query(rk_{l1}+1,rk_{l2}),r1-l1+1,r2-l2+1\}$。

感觉是对的。