String_Search.H File Reference

Classical pattern searching algorithms over strings. More...

#include <cstdint>
#include <algorithm>
#include <string>
#include <string_view>
#include <array>
#include <tpl_array.H>

Include dependency graph for String_Search.H:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Namespaces
namespace	Aleph
	Main namespace for Aleph-w library functions.
namespace	Aleph::string_search_detail

Functions
Array< size_t >	Aleph::string_search_detail::all_match_positions (const size_t text_size)
	Generate an array of all positions from 0 to text_size.
bool	Aleph::string_search_detail::find_unused_delimiter (const std::string_view a, const std::string_view b, char &delimiter)
	Find a character not present in either string.
bool	Aleph::string_search_detail::equals_at (const std::string_view text, const std::string_view pattern, const size_t pos)
	Check if pattern matches text at given position.
Array< size_t >	Aleph::kmp_prefix_function (const std::string_view pattern)
	Prefix-function used by KMP.
Array< size_t >	Aleph::kmp_search (const std::string_view text, const std::string_view pattern)
	Find all occurrences of a pattern using KMP.
Array< size_t >	Aleph::z_algorithm (const std::string_view s)
	Compute Z-array for a string.
Array< size_t >	Aleph::z_search (const std::string_view text, const std::string_view pattern)
	Find all occurrences of a pattern using the Z-algorithm.
Array< size_t >	Aleph::boyer_moore_horspool_search (const std::string_view text, const std::string_view pattern)
	Find all occurrences using Boyer-Moore-Horspool.
Array< size_t >	Aleph::rabin_karp_search (const std::string_view text, const std::string_view pattern, const uint64_t base=911382323ull)
	Find all occurrences using Rabin-Karp with rolling hash.

Detailed Description

Classical pattern searching algorithms over strings.

This header provides single-pattern matching algorithms commonly used in competitive programming and production text processing:

• Knuth-Morris-Pratt (KMP)
• Z-algorithm
• Boyer-Moore-Horspool
• Rabin-Karp (rolling hash with exact verification)

All APIs return all match positions (0-based), including overlaps.

Definition in file String_Search.H.