Program Listing for File AhoCorasick.h

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

/*--------------------------------------------------------------------------*/
/*--------------------------- File AhoCorasick.h ---------------------------*/
/*--------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------*/
/*----------------------------- DEFINITIONS --------------------------------*/
/*--------------------------------------------------------------------------*/

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

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

#include "ADS/Contract.h"

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

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

namespace ADS {

/*--------------------------------------------------------------------------*/
/*--------------------------- CLASS AhoCorasick ----------------------------*/
/*--------------------------------------------------------------------------*/

class AhoCorasick {

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

 AhoCorasick( void );

 explicit AhoCorasick( const std::vector< std::string > & P );

 std::size_t add( std::string_view P );

 void build( void );

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

 [[nodiscard]] std::size_t count( std::string_view T ) const;

 template< class F >
 void forEach( std::string_view T , F && report ) const {
  scan( T , [ & ]( std::size_t j , std::uint32_t id ) {
   report( j + 1 - f_P[ id ].size() , std::size_t( id ) ); } );
  }

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

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

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

 template< class F >
 void scan( std::string_view T , F && report ) const;

 std::vector< std::string > f_P;
 std::vector< std::array< std::uint32_t , 256 > > f_go;
 std::vector< std::uint32_t > f_fail;
 std::vector< std::uint32_t > f_out;
 std::vector< std::vector< std::uint32_t > > f_ends;
 bool f_built = true;

 };  // end( class AhoCorasick )

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

}  // end( namespace ADS )

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

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

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

#endif  /* AhoCorasick.h included */

/*--------------------------------------------------------------------------*/
/*------------------------ End File AhoCorasick.h --------------------------*/
/*--------------------------------------------------------------------------*/