构建字符串的FM-index 并查询子字符串c++代码_fm index

FM-index（Full-text index in Minute space）是一种用于快速搜索和检索大量文本数据的数据结构。它结合了压缩后缀数组（Compressed Suffix Array）和波束树（Wavelet Tree）的优点，旨在实现高效的全文搜索操作。

本示例使用了第三方库 sdsl-lite 来实现 FM-index，该库提供了一些高效的数据结构和算法用于压缩后缀数组和 FM-index 的构建和查询。

#include <iostream>
#include <string>
#include <vector>
#include <sdsl/suffix_arrays.hpp>
 
using namespace std;
using namespace sdsl;
 
int main() {
    // 输入字符串
    string text = "banana";
    
    /*
     csa 代表 "Compressed Suffix Array"，即压缩后缀数组
     wt 代表 "Wavelet Tree"，即波束树。
     huff 代表 "Huffman Coding"
     csa_wt<wt_huff<>> 构建一个基于压缩后缀数组和基于霍夫曼编码的波束树的 FM-index
     */
    csa_wt<wt_huff<>> fm_index;
    
    // 构建后缀数组和 FM-index
    construct_im(fm_index, text.c_str(), 1);
 
    // 查询子字符串
    string query = "ana";
    auto occs = locate(fm_index, query.c_str(), query.c_str() + query.size());
 
    // 输出子字符串的出现位置
    cout << "Positions of \"" << query << "\": ";
    for (auto occ : occs) {
        cout << occ << " ";
    }
    cout << endl;
 
    return 0;
}