One Aho-Corasick trie/DFA node: a dense 256-entry goto row plus fail/output links. More...

#include <aho_corasick.hpp>

Public Member Functions
	ac_node ()
	A trie node with no edges yet: every goto_ entry is -1 until ac_automaton::build makes the row total.

Public Attributes
std::array< std::int32_t, 256 >	goto_ {}
	Trie edge (build) / total DFA transition (post-build).

std::int32_t	fail {0}
	Fail link: the longest proper suffix of this state that is also a trie prefix.

std::int32_t	pattern_id {-1}
	Smallest branch id ending here, or -1.

std::int32_t	pattern_len {0}
	Byte length of the pattern ending here; 0 when none does.

std::int32_t	output_link {-1}
	Next (strictly shorter) pattern-ending state on the fail chain.

Detailed Description

One Aho-Corasick trie/DFA node: a dense 256-entry goto row plus fail/output links.

goto_ starts as a sparse trie edge set (missing = -1) during ac_automaton::build and ends as a TOTAL transition function (goto-function-as-DFA): every entry is a valid state index once construction finishes, so a search-time lookup is a single array read with no fail-chain walk. Dense only, no sparse or hybrid row: this engine is built for literal alternations of tens of nodes, where the whole table is a few kilobytes, and a sparse row would trade that certain cost for a lookup that is no longer one read.

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

include/real/engine/aho_corasick.hpp

Public Member Functions

Public Attributes

Detailed Description