后缀数组

后缀数组在文本串中寻找子串在文本串 $T$ 中寻找模式串 $S$，那么 $S$ 一定是 $T$ 的某个后缀的前缀，后缀排序后，在 $SA$ 中二分 $S$ 的位置，每次 $check$ 比较时间 $O (|S|)$，总时间复杂度 $O (|S| \log |T|)$ 比较两个子串的大小关系比较 $S$ 的子串 $A = S[l_1…r_1], B = S[l_2…r_2]$ 的大小关系 若 $lcp (l_1, l_2) \ge \min (|A|, |B|)$，则 $A < B \Longleftrightarrow |A| < |B|$，反之 $A < B \Longleftrightarrow rk_{l_1} < rk_{l_2}$ 本质不同子串数目设字符串 $S$ 长度为 $n$ $ans = \frac{n(n + 1)}2 - \sum\limits_{i = 2}^n height[i]$ 从字符串首或尾取字符构成最小字典序的字符串[USACO07DEC]Best Cow Line G 最基本贪心，若两端字符不同，优先取大的，那么问题就在于两端相 ...