按子串字典序排序的文本索引是否有通用名称？

架构老林

2026-7-2

后缀数组：你描述的经典数据结构名称

你提到的这种按所有从文本各位置起始、延续至末尾的子串（即文本的后缀）字典序排序的索引，通用名称是后缀数组（Suffix Array）。

后缀数组的核心是一个存储文本所有后缀起始位置的数组，且这些位置按对应后缀的字典序排列。它具备你提到的所有特性：

可通过二分查找快速定位目标子串，搜索效率高效
排序后相似的后缀会相邻排列，便于查找相似字符串

你的代码实现了后缀数组的直观构建方式——直接对所有后缀的起始位置进行排序，但这种方法的时间复杂度较高（O(n² log n)，n为文本长度）。实际场景中通常会使用更高效的构建算法，比如倍增法（O(n log² n)）或SA-IS算法（线性时间O(n)）。

你的代码实现

#include <algorithm>
#include <iostream>
#include <ranges>
#include <vector>

auto make_index_projection_for_subrange = []<std::ranges::random_access_range R>(R & range) {
    return [&range](std::ranges::range_difference_t<R> i) -> decltype(auto) {
        return std::ranges::subrange(std::ranges::begin(range)+i, std::ranges::end(range));
        };
};

int main()
{
    const std::string s1 = "abdbc";
    std::vector i1{0,1,2,3,4};
    
    //Sort by substring from the char to the end
    auto proj = make_index_projection_for_subrange(s1);

    std::ranges::sort(i1, std::ranges::lexicographical_compare,proj);
    std::ranges::copy(i1, std::ostream_iterator<int>(std::cout));
    std::cout << std::endl;

    for(auto i: i1){
        std::cout << std::string(s1.begin()+i, s1.end()) << std::endl;
    }
}