字典排序的索引有一些通用名称吗?
我有文本和索引,按所有子字符串的字典顺序排序,这些子字符串从特定位置开始一直到文本末尾。
让我们考虑一下代码:
#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;
}
}
查看演示;它提供以下结果:
03142
abdbc
公元前
BDBC
dbc
所有子字符串现在都按字母顺序排序,并且搜索速度至少与二分搜索一样快。如果需要找到相似的字符串,只需穿过相邻的行即可。
我称其为“相邻索引”,因为所有相似的子字符串都彼此相邻,但我猜这是一个具有通用名称的经典结构。