libsemigroups::aho_corasick Namespace Reference

Defined in aho-corasick.hpp.

This namespace contains various helper functions for the class AhoCorasick. These functions could be functions of AhoCorasick but they only use public member functions of AhoCorasick, and so they are declared as free functions instead.

Typedefs
using	index_type = AhoCorasick::index_type
	Alias for the index of a node in the trie.

Functions
template<typename Word>
index_type	add_word (AhoCorasick &ac, Word const &w)
	Add a word to the trie of ac.
template<typename Word>
index_type	add_word_no_checks (AhoCorasick &ac, Word const &w)
	Add a word to the trie of ac.
Dot	dot (AhoCorasick &ac)
	Construct a dot object of ac.
template<typename Word>
index_type	rm_word (AhoCorasick &ac, Word const &w)
	Remove a word from the trie of ac.
template<typename Word>
index_type	rm_word_no_checks (AhoCorasick &ac, Word const &w)
	Remove a word from the trie of ac.
template<typename Iterator>
index_type	traverse_word (AhoCorasick const &ac, index_type start, Iterator first, Iterator last)
	Traverse the trie of ac using suffix links where necessary.
template<typename Word>
index_type	traverse_word (AhoCorasick const &ac, index_type start, Word const &w)
	Traverse the trie of ac using suffix links where necessary.
template<typename Iterator>
index_type	traverse_word (AhoCorasick const &ac, Iterator first, Iterator last)
	Traverse the trie of ac from the root using suffix links where necessary.
template<typename Word>
index_type	traverse_word (AhoCorasick const &ac, Word const &w)
	Traverse the trie of ac from the root using suffix links where necessary.
template<typename Iterator>
index_type	traverse_word_no_checks (AhoCorasick const &ac, index_type start, Iterator first, Iterator last)
	Traverse the trie of ac using suffix links where necessary.
index_type	traverse_word_no_checks (AhoCorasick const &ac, index_type start, word_type const &w)
	Traverse the trie of ac using suffix links where necessary.

Function Documentation

add_word()

template<typename Word>

index_type add_word	(	AhoCorasick &	ac,
		Word const &	w )

This function performs the same as ac.add_word(w.begin(), w.end()).

Template Parameters

Word	the type of the 2nd parameter w.

Parameters

ac	AhoCorasick object to add the word to.
w	the word to add.

Returns

An index_type corresponding to the final node added to the ac.

Exceptions

LibsemigroupsException

if the word w corresponds to an existing terminal node in the trie.

Complexity

Linear in the length of w.

See also

add_word.

add_word_no_checks()

template<typename Word>

index_type add_word_no_checks	(	AhoCorasick &	ac,
		Word const &	w )

This function performs the same as ac.add_word_no_checks(w.begin(), w.end()).

Template Parameters

Word	the type of the 2nd parameter w.

Parameters

ac	AhoCorasick object to add the word to.
w	the word to add.

Returns

An index_type corresponding to the final node added to the ac.

Exceptions

This function guarantees not to throw a LibsemigroupsException.

Complexity

Linear in the length of w.

See also

add_word_no_checks.

dot()

Dot dot ( AhoCorasick & ac )

nodiscard

Construct a Dot object representing the trie of ac with suffix links.

rm_word()

template<typename Word>

index_type rm_word	(	AhoCorasick &	ac,
		Word const &	w )

This function performs the same as ac.rm_word(w.begin(), w.end()).

Template Parameters

Word	the type of the 2nd parameter w.

Parameters

ac	AhoCorasick object to remove the word from.
w	the word to remove.

Returns

An index_type corresponding to the node with signature equal to w.

Exceptions

LibsemigroupsException

if the word w does not correspond to an existing terminal node in the trie.

Complexity

Linear in the length of w.

See also

rm_word.

rm_word_no_checks()

template<typename Word>

index_type rm_word_no_checks	(	AhoCorasick &	ac,
		Word const &	w )

This function performs the same as ac.rm_word_no_checks(w.begin(), w.end()).

Template Parameters

Word	the type of the 2nd parameter w.

Parameters

ac	AhoCorasick object to remove the word from.
w	the word to remove.

Returns

An index_type corresponding to the node with signature equal to w.

Exceptions

This function guarantees not to throw a LibsemigroupsException.

Complexity

Linear in the length of w.

See also

rm_word_no_checks.

traverse_word() [1/4]

template<typename Iterator>

index_type traverse_word ( AhoCorasick const & ac, index_type start, Iterator first, Iterator last )

nodiscard

After validating start with respect to ac, this function performs the same as traverse_word_no_checks(ac, start, first, last).

Exceptions

LibsemigroupsException

if ac.throw_if_node_index_not_active(start) throws.

See also

traverse_word_no_checks(AhoCorasick const& ac, index_type start, Iterator first, Iterator last), throw_if_node_index_not_active.

traverse_word() [2/4]

template<typename Word>

index_type traverse_word ( AhoCorasick const & ac, index_type start, Word const & w )

inlinenodiscard

This function performs the same as traverse_word(ac, start, w.cbegin(), w.cend()).

See also

traverse_word(AhoCorasick const& ac, index_type start, Iterator first, Iterator last).

traverse_word() [3/4]

template<typename Iterator>

index_type traverse_word ( AhoCorasick const & ac, Iterator first, Iterator last )

nodiscard

This function performs the same as traverse_word_no_checks(ac, AhoCorasick::root, first, last).

Note

There is no _no_checks suffix here as AhoCorasick::root is always a valid node of a trie, and therefore no checks are needed.

See also

traverse_word_no_checks(AhoCorasick const& ac, index_type start, Iterator first, Iterator last).

traverse_word() [4/4]

template<typename Word>

index_type traverse_word ( AhoCorasick const & ac, Word const & w )

nodiscard

This function performs the same as traverse_word_no_checks(ac, AhoCorasick::root, w.cbegin(), w.end()).

Note

There is no _no_checks suffix here as AhoCorasick::root is always a valid node of a trie, and therefore no checks are needed.

See also

traverse_word_no_checks(AhoCorasick const& ac, index_type start, Iterator first, Iterator last).

traverse_word_no_checks() [1/2]

template<typename Iterator>

index_type traverse_word_no_checks ( AhoCorasick const & ac, index_type start, Iterator first, Iterator last )

nodiscard

This function traverses the trie of ac, starting at the node with index start, and traversing using the letters in the word corresponding to first and last.

Template Parameters

Iterator

the type of the 2nd and 3rd parameters.

Parameters

ac	AhoCorasick object to traverse.
start	the index of the node to first traverse from.
first	iterator pointing to the first letter of the word to traverse.
last	one beyond the last letter of the word to traverse.

Returns

An value of type index_type.

Exceptions

This function guarantees not to throw a LibsemigroupsException.

Warning

This function does no checks on its arguments whatsoever. In particular, if the index start is greater than the number of nodes that have ever been created, then bad things will happen.

See also

traverse_no_checks.

traverse_word_no_checks() [2/2]

index_type traverse_word_no_checks ( AhoCorasick const & ac, index_type start, word_type const & w )

inlinenodiscard

This function performs the same as traverse_word_no_checks(ac, start, w.cbegin(), w.cend()).

See also

traverse_word_no_checks(AhoCorasick const& ac, index_type start, Iterator first, Iterator last).