String Algorithms

String algorithms operate on sequences of symbols. Before analyzing them, define the symbol model: bytes, Unicode code points, UTF-16 code units, normalized text, or locale-aware grapheme clusters are not interchangeable.

Topics

• Exact string matching
• Tries for prefix indexing

Other important families include suffix arrays/trees, edit distance, longest common subsequence, multiple-pattern matching, compression, and parsing.

Variables

This section uses n for text length, m for pattern length, and Σ for the alphabet. Length always refers to the page's chosen symbol representation.