SuffixArray

class numpy::SuffixArray

numpy C++ class.

Example

#include <numpy/np_ndarray.h>
using namespace numpy;

// Use SuffixArray
SuffixArray obj;
// ... operations ...

Other Methods

Signature	Return Type	Location	Example
static std::vector<size_t> build_suffix_array(const StringType& text)	std::vector<size_t>	np_string_sort.h:332	View
static std::vector<size_t> find_pattern(const StringType& text, const std::vector<size_t>& suffix_array, const StringType& pattern)	std::vector<size_t>	np_string_sort.h:376	View

Code Examples

The following examples are extracted from the test suite.

build_suffix_array (np_test_1_all.cpp:12657)

    // std::cout << "LSD radix sort test passed" << std::endl;

    std::cout << " -> tests passed" << std::endl;
  }

  void test_suffix_array_construction() {
    std::cout << "========= test_suffix_array_construction =======================";

    std::string text = "banana";
    auto suffix_array = SuffixArray::build_suffix_array(text);

    if (!(suffix_array.size() == text.size())) {
        std::string description = std::string("test_suffix_array_construction():") + __FILE__ + ":" + std::to_string(__LINE__) + ": !(suffix_array.size() == text.size())";
        std::cout << std::string("[FAIL] ") + description << std::endl;
        throw std::runtime_error(description);
    }

    // Verify suffixes are properly sorted
    for (size_t i = 1; i < suffix_array.size(); ++i) {
      std::string prev_suffix = text.substr(suffix_array[i - 1]);

find_pattern (np_test_1_all.cpp:12688)

    std::cout << " -> tests passed" << std::endl;
  }

  void test_suffix_array_pattern_search() {
    std::cout << "========= test_suffix_array_pattern_search =======================";

    std::string text = "abananabandana";
    auto suffix_array = SuffixArray::build_suffix_array(text);

    // Search for pattern "ana"
    auto positions = SuffixArray::find_pattern(text, suffix_array, std::string("ana"));

    // "ana" appears at positions 1, 3, 5, 9, 11 in "abananabandana"
    if (!(!positions.empty())) {
        std::string description = std::string("test_suffix_array_pattern_search():") + __FILE__ + ":" + std::to_string(__LINE__) + ": !(!positions.empty())";
        std::cout << std::string("[FAIL] ") + description << std::endl;
        throw std::runtime_error(description);
    }

    // Verify found positions are correct
    for (size_t pos : positions) {