应用
任意子串 \(\text{LCP}\) 长度
$LCP(i,j) = \min\limits_{k=rk_i+1}^{rk_j} ht_k $
运用此性质，可以有通用套路：\(\text{Height}\) 分段，下面题目会有讲解。
练习题
P2743 [USACO5.1] 乐曲主题Musical Themes
最长不重复多次出现子串。\(\text{Height}\) 分段经典题目。
首先求出原串的 \(\text{Height}\)，然后二分答案，check 时可以将 \(ht\) 数组分为若干个极大的 \([l,r]\) 区间，使得区间都满足 $ i \in [l+1,r] , ht_i \geq mid$。这样的话，对于每一个区间内所有后缀的 \(\text{LCP}\) 都是大于等于 \(mid\) 的，这样就只需要对于每一段求出 \(sa\) 数组的 \(\max\) 和 \(\min\)，若两者相减大于等于 \(mid\)，则不相交。
UVA11107 Life Forms
将所有串用分隔符隔开后拼到一起。
同理也可以二分，然后分段。多处理一个 \(bel\) 数组，表示排名 \(i\) 的后缀来自的原串编号，分段后处理一个桶即可。