String

Pattern matching, hashing, automata, and string factorization.

Headers

Header	Summary
aho_corasick.hpp	Aho-Corasick automaton for an integer alphabet [0, sigma).
deque_palindromic_tree.hpp	Maintain all distinct palindromic substrings under pushes and pops at both ends. Every active palindrome is a node with a suffix link, while each text position stores the longest palindrome beginning or ending there. A quick link skips suffix-link runs whose next extension character is the same, so a new extendable boundary palindrome is found logarithmically. Surface counters and incoming suffix-link counters identify a node exactly when its last occurrence disappears, allowing an end deletion to undo only local certificates. Two reversed vectors provide amortized constant-time deque rebalancing while retaining indexed character access.
kmp.hpp	Compute the prefix function of a sequence in O(n).
longest_common_substring.hpp	Return positions of one longest common contiguous substring.
lyndon_factor.hpp	Compute the Lyndon factorization of a sequence.
manacher.hpp	Compute palindrome radii for all centers (characters and gaps) using Manacher's algorithm.
minimal_string.hpp	Find the starting index of the lexicographically smallest rotation.
online_z_algo.hpp	Online Z-algorithm: compute Z-values incrementally as characters are appended.
palindromic_automaton.hpp	Palindromic automaton (Eertree) for enumerating distinct palindromic substrings.
prefix_substring_lcs.hpp	Answer LCS lengths between prefixes of one sequence and substrings of another. The dynamic-programming grid is represented by its seaweed permutation: after adding one symbol of the first sequence, a single scan swaps boundary endpoints exactly where equality or crossing changes the next LCS row. For a fixed prefix, the LCS deficit of [left, right) equals the number of active endpoints entering that interval from before left. Sweeping right and counting endpoint positions with a Fenwick tree answers every query assigned to that prefix without storing the quadratic DP table.
rolling_hash.hpp	Length-aware rolling hashes modulo 2^61-1 for substring comparison, concatenation, and longest-common-extension queries.
runs.hpp	Compute all runs (maximal periodicities) in a sequence.
suffix_array_query.hpp	Suffix array with O(1) suffix LCP queries and lexicographic pattern interval/search over a fixed string.
suffix_automaton.hpp	Suffix automaton (SAM) for online suffix structure construction. Each state represents substrings sharing an end-position set. Extending by one character redirects missing transitions along suffix links; when the target has excessive length, a clone splits its end-position class while preserving transitions, keeping at most two new states per character.
wildcard_matching.hpp	Return every alignment where text and pattern agree outside the wildcard character, using exact integer convolutions in O(n log n).