Program Listing for File SuffixAutomaton.h

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

/*--------------------------------------------------------------------------*/
/*------------------------- File SuffixAutomaton.h -------------------------*/
/*--------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------*/
/*----------------------------- DEFINITIONS --------------------------------*/
/*--------------------------------------------------------------------------*/

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

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

#include "ADS/Contract.h"

#include <cstddef>
#include <cstdint>
#include <string_view>
#include <utility>
#include <vector>

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

namespace ADS {

/*--------------------------------------------------------------------------*/
/*------------------------ CLASS SuffixAutomaton ---------------------------*/
/*--------------------------------------------------------------------------*/

class SuffixAutomaton {

/*--------------------------------------------------------------------------*/
 public:

 SuffixAutomaton( void );

 explicit SuffixAutomaton( std::string_view S );

 void extend( unsigned char c );

 [[nodiscard]] bool contains( std::string_view P ) const;

 [[nodiscard]] std::size_t occurrences( std::string_view P ) const;

 [[nodiscard]] std::size_t distinctSubstrings( void ) const;

 [[nodiscard]] std::pair< std::size_t , std::size_t >
  longestCommonSubstring( std::string_view T ) const;

 [[nodiscard]] std::size_t states( void ) const { return( f_len.size() ); }

 [[nodiscard]] std::size_t size( void ) const { return( f_n ); }

/*--------------------------------------------------------------------------*/
 private:

 [[nodiscard]] std::uint32_t next( std::uint32_t v , unsigned char c ) const;

 void counts( void ) const;

 static constexpr std::uint32_t none = ~std::uint32_t( 0 );

 std::vector< std::size_t > f_len;
 std::vector< std::uint32_t > f_link;
 std::vector< std::vector< std::pair< unsigned char , std::uint32_t > > >
  f_next;
 std::vector< std::uint8_t > f_prefix;
 std::uint32_t f_last = 0;
 std::size_t f_n = 0;
 mutable std::vector< std::size_t > f_count;

 };  // end( class SuffixAutomaton )

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

}  // end( namespace ADS )

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

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

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

#endif  /* SuffixAutomaton.h included */

/*--------------------------------------------------------------------------*/
/*----------------------- End File SuffixAutomaton.h -----------------------*/
/*--------------------------------------------------------------------------*/