longest_repeated_substring.hpp

Go to the documentation of this file.

// Andrew Naplavkov
 
#ifndef STEP20_LONGEST_REPEATED_SUBSTRING_HPP
#define STEP20_LONGEST_REPEATED_SUBSTRING_HPP
 
#include "suffix_array.hpp"
#include "suffix_tree.hpp"
 
namespace step20 {
 
 
template <class... Ts>
auto longest_repeated_substring(const enhanced_suffix_array<Ts...>& arr)
    -> std::basic_string_view<typename enhanced_suffix_array<Ts...>::value_type>
{
    auto first = arr.data();
    auto last = first + arr.size();
    auto result = std::basic_string_view{last, last};
    auto lcp = arr.lcp_array();
    auto max = std::ranges::max_element(lcp);
    if (max != lcp.end() && *max > 0) {
        auto pos = arr[max - lcp.begin()];
        result = std::basic_string_view{first + pos, first + pos + *max};
    }
    return result;
}
 
 
template <class... Ts>
auto longest_repeated_substring(const suffix_tree<Ts...>& tree)
    -> std::basic_string_view<typename suffix_tree<Ts...>::value_type>
{
    auto first = tree.data();
    auto last = first + tree.size();
    auto result = std::basic_string_view{last, last};
    if (auto start = tree.find(result))
        for (auto edge : tree.depth_first_search(*start)) {
            if (tree.leaf(edge.child_node) || edge.labels_len <= result.size())
                continue;
            auto labels = tree.labels(edge);
            result = std::basic_string_view{first + labels.first,
                                            first + labels.last};
        }
    return result;
}
 
}  // namespace step20
 
#endif  // STEP20_LONGEST_REPEATED_SUBSTRING_HPP