Acore::AhoCorasick< CharT > Class Template Reference

Multi-pattern substring matcher. More...

#include "AhoCorasick.h"

Classes
struct	Node

Public Types
using	StringType = std::basic_string< CharT >
using	StringViewType = std::basic_string_view< CharT >

Public Member Functions
	AhoCorasick ()
void	Insert (StringViewType pattern)
void	Build ()
bool	ContainsAny (StringViewType text) const
bool	Empty () const
void	Clear ()

Private Attributes
std::vector< Node >	_nodes

Detailed Description

template<typename CharT>
class Acore::AhoCorasick< CharT >

Multi-pattern substring matcher.

Insert all patterns, call Build() once, then query in O(text length) regardless of pattern count. Insertion after Build() is not supported (it would invalidate failure links — call Build() again if you must).

Matching is exact on the CharT alphabet — pre-lowercase patterns and inputs in the caller if you need case-insensitive matching.

Usage: Acore::AhoCorasick<wchar_t> a; a.Insert(L"foo"); a.Insert(L"bar"); a.Build(); bool hit = a.ContainsAny(L"the bar is open"); // -> true

Member Typedef Documentation

StringType

template<typename CharT >

using Acore::AhoCorasick< CharT >::StringType = std::basic_string<CharT>

StringViewType

template<typename CharT >

using Acore::AhoCorasick< CharT >::StringViewType = std::basic_string_view<CharT>

Constructor & Destructor Documentation

AhoCorasick()

template<typename CharT >

Acore::AhoCorasick< CharT >::AhoCorasick ( )

inline

{ _nodes.emplace_back(); }

References Acore::AhoCorasick< CharT >::_nodes.

Member Function Documentation

Build()

template<typename CharT >

void Acore::AhoCorasick< CharT >::Build ( )

inline

        {
            std::queue<uint32> bfs;
            for (auto const& kv : _nodes[0].next)
            {
                _nodes[kv.second].fail = 0;
                bfs.push(kv.second);
            }
 
            while (!bfs.empty())
            {
                uint32 u = bfs.front();
                bfs.pop();
 
                for (auto const& kv : _nodes[u].next)
                {
                    CharT c = kv.first;
                    uint32 v = kv.second;
 
                    uint32 f = _nodes[u].fail;
                    while (f != 0 && _nodes[f].next.find(c) == _nodes[f].next.end())
                        f = _nodes[f].fail;
 
                    auto it = _nodes[f].next.find(c);
                    _nodes[v].fail = (it != _nodes[f].next.end() && it->second != v) ? it->second : 0;
 
                    if (_nodes[_nodes[v].fail].output)
                        _nodes[v].output = true;
 
                    bfs.push(v);
                }
            }
        }

References Acore::AhoCorasick< CharT >::_nodes.

Clear()

template<typename CharT >

void Acore::AhoCorasick< CharT >::Clear ( )

inline

        {
            _nodes.clear();
            _nodes.emplace_back();
        }

References Acore::AhoCorasick< CharT >::_nodes.

ContainsAny()

template<typename CharT >

bool Acore::AhoCorasick< CharT >::ContainsAny ( StringViewType  text ) const

inline

        {
            if (_nodes.size() <= 1)
                return false;
 
            uint32 cur = 0;
            for (CharT c : text)
            {
                while (cur != 0 && _nodes[cur].next.find(c) == _nodes[cur].next.end())
                    cur = _nodes[cur].fail;
 
                auto it = _nodes[cur].next.find(c);
                if (it != _nodes[cur].next.end())
                    cur = it->second;
 
                if (_nodes[cur].output)
                    return true;
            }
            return false;
        }

References Acore::AhoCorasick< CharT >::_nodes.

Empty()

template<typename CharT >

bool Acore::AhoCorasick< CharT >::Empty ( ) const

inline

{ return _nodes.size() <= 1; }

References Acore::AhoCorasick< CharT >::_nodes.

Insert()

template<typename CharT >

void Acore::AhoCorasick< CharT >::Insert ( StringViewType  pattern )

inline

        {
            if (pattern.empty())
                return;
 
            uint32 cur = 0;
            for (CharT c : pattern)
            {
                auto it = _nodes[cur].next.find(c);
                if (it != _nodes[cur].next.end())
                {
                    cur = it->second;
                    continue;
                }
 
                uint32 idx = static_cast<uint32>(_nodes.size());
                _nodes.emplace_back();
                _nodes[cur].next.emplace(c, idx);
                cur = idx;
            }
            _nodes[cur].output = true;
        }

References Acore::AhoCorasick< CharT >::_nodes.

Member Data Documentation

_nodes

template<typename CharT >

std::vector<Node> Acore::AhoCorasick< CharT >::_nodes

private

Referenced by Acore::AhoCorasick< CharT >::AhoCorasick(), Acore::AhoCorasick< CharT >::Build(), Acore::AhoCorasick< CharT >::Clear(), Acore::AhoCorasick< CharT >::ContainsAny(), Acore::AhoCorasick< CharT >::Empty(), and Acore::AhoCorasick< CharT >::Insert().

---

The documentation for this class was generated from the following file:

• azerothcore-wotlk/src/common/Utilities/AhoCorasick.h