问题分析

给定一个长度为 $N$ 的字符串 $S$，要求找出字典序第 $K$ 小的子串。参数 $T$ 控制计数方式：

$T = 0$：不同位置的相同子串算作一个

$T = 1$：不同位置的相同子串算作多个

算法思路

总体架构

代码使用后缀数组（Suffix Array）作为核心数据结构，然后根据 $T$ 的值分别处理两种情况。

关键数据结构：后缀数组

后缀数组 $sa[i]$ 表示将所有后缀按字典序排序后，第 $i$ 小的后缀在原字符串中的起始位置。

相关数组：

$sa[i]$：排名第 $i$ 的后缀起始位置

$rk[i]$：起始位置为 $i$ 的后缀的排名

$ht[i]$：$sa[i]$ 与 $sa[i-1]$ 的最长公共前缀长度

情况1：$T = 0$（相同子串算一个）

算法思路：

1.按字典序遍历所有后缀

2.对于每个后缀 $sa[i]$，它贡献的新子串数量为：$(n - sa[i] + 1 - ht[i])$

$n - sa[i] + 1$：该后缀的所有前缀（即所有以该位置开始的子串）

减去 $ht[i]$：去掉与上一个后缀重复的前缀

3.当累计的新子串数量达到 $K$ 时，输出对应的子串

情况2：$T = 1$（相同子串算多个）

算法思路：

1.预处理前缀和数组 $sum[i] = \sum_{j=1}^{i} (n - sa[j] + 1)$，表示前 $i$ 个后缀包含的所有子串总数

2.使用二分查找确定第 $K$ 小的子串：

维护当前搜索范围 $[L, R]$，表示可能包含目标子串的后缀排名区间

逐位确定子串的每个字符：

对于每个可能的字符 $c$，在 $[L, R]$ 中二分查找以 $c$ 开头的后缀范围

计算该字符对应的子串总数

根据 $K$ 的值缩小搜索范围

复杂度分析

后缀数组构建：$O(N \log N)$

$T = 0$ 情况：$O(N)$

$T = 1$ 情况：$O(N \log N)$

总体复杂度：$O(N \log N)$，可以处理 $N \leq 5 \times 10^5$ 的数据规模。

总结

本题通过后缀数组高效处理了字符串子串的字典序排序问题，针对两种不同的计数需求设计了相应的算法：

$T = 0$：利用 $ht$ 数组去重，线性扫描

$T = 1$：结合前缀和与二分查找，逐位确定目标子串