Program Listing for File SuffixApplications.h

↰ Return to documentation for file (ADS/string/SuffixApplications.h)

/*--------------------------------------------------------------------------*/
/*----------------------- File SuffixApplications.h ------------------------*/
/*--------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------*/
/*----------------------------- DEFINITIONS --------------------------------*/
/*--------------------------------------------------------------------------*/

#ifndef __ADS_SuffixApplications
 #define __ADS_SuffixApplications
                      /* self-identification: #endif constant */

/*--------------------------------------------------------------------------*/
/*------------------------------ INCLUDES ----------------------------------*/
/*--------------------------------------------------------------------------*/

#include "ADS/Contract.h"
#include "ADS/string/SuffixArray.h"
#include "ADS/string/SuffixTree.h"

#include <algorithm>
#include <cstddef>
#include <cstdint>
#include <optional>
#include <string>
#include <string_view>
#include <utility>
#include <vector>

/*--------------------------------------------------------------------------*/
/*--------------------------- NAMESPACE ------------------------------------*/
/*--------------------------------------------------------------------------*/

namespace ADS {

struct CopyPhrase {
 std::size_t distance = 0;
 std::size_t length = 0;
 std::optional< char > next;
 friend bool operator==( const CopyPhrase & , const CopyPhrase & ) = default;
 };

[[nodiscard]] inline std::pair< std::size_t , std::size_t >
                         longestRepeatedSubstring( const SuffixArray & SA );

[[nodiscard]] inline std::optional< std::size_t > repeatedSubstring(
                  const SuffixArray & SA , std::size_t L , std::size_t C );

[[nodiscard]] inline std::uint64_t distinctSubstrings(
                                                   const SuffixArray & SA );

[[nodiscard]] inline std::string longestCommonSubstring(
                       const std::vector< std::string > & S , std::size_t k );

[[nodiscard]] inline std::vector< std::pair< std::size_t , std::size_t > >
                                      maximalRepeats( const SuffixTree & ST );

[[nodiscard]] inline bool proximity( const SuffixArray & SA ,
                                     std::string_view P , std::string_view Q ,
                                     std::size_t k );

[[nodiscard]] inline std::vector< std::size_t > kMismatches(
                                        std::string_view T ,
                                        std::string_view P , std::size_t k );

[[nodiscard]] inline std::vector< CopyPhrase > lz77ByTree(
                                                        std::string_view T );

[[nodiscard]] inline std::string decodeCopyPhrases(
                                     const std::vector< CopyPhrase > & Z );

/*--------------------------------------------------------------------------*/

}  // end( namespace ADS )

/*--------------------------------------------------------------------------*/
/*-------------------------- IMPLEMENTATION --------------------------------*/
/*--------------------------------------------------------------------------*/

#include "ADS/string/impl/SuffixApplications.tpp"

/*--------------------------------------------------------------------------*/

#endif  /* SuffixApplications.h included */

/*--------------------------------------------------------------------------*/
/*--------------------- End File SuffixApplications.h ----------------------*/
/*--------------------------------------------------------------------------*/