String Algorithms

Try every alignment of the pattern against the text and compare character by character.

Linear-time pattern matching that never re-reads text characters, using a precomputed failure (LPS) table of the pattern.

Compare a rolling hash of each text window with the pattern hash and verify only on hash hits.

Compute for every position the length of the longest substring starting there that matches a prefix of the string, in linear time.

Compute the palindrome radius around every center in O(n) by reusing mirrored radii inside the rightmost known palindrome.

Precompute prefix hashes so the hash of any substring — and hence substring equality — can be evaluated in O(1).

Search a text for every word of a dictionary simultaneously by walking a trie augmented with KMP-style failure links.

Sort all suffixes of a string by index; with the LCP array it answers substring search, distinct-substring counts and longest-repeat queries.

A compressed trie of all suffixes of a string; answers substring search in O(m), longest repeat and distinct-substring counts directly from its structure.