5.11 Rolling Hashes
Compute hash values for sliding windows over a sequence in constant time by incrementally updating rather than recomputing.
Tag
Strings
27 notes
2.25 Boundary Conditions
Boundary conditions define the valid domain of indices, ranges, and states in an algorithm.
2.24 Common Patterns
Array and string problems often look different on the surface, but many reduce to a small number of reusable patterns.
2.23 Flood Fill
Flood fill explores a connected region in a grid starting from a seed cell and marks or transforms all cells that belong to the same region.
2.22 Spiral Traversal
Spiral traversal visits a matrix layer by layer, moving right across the top row, down the right column, left across the bottom row, and up the left column,...
2.21 Matrix Traversal
Matrix traversal processes a two-dimensional array in a defined order.
2.20 Tries
A trie is a tree structure for storing a set of strings so that common prefixes are shared.
2.19 Parsing Expressions
Parsing expressions converts a sequence of tokens into a structured form that reflects operator precedence and associativity.
2.18 String Comparison
String comparison determines the ordering or equality of two strings.
2.17 Rolling Hashes
Rolling hashes assign numeric fingerprints to substrings so that many substring comparisons can be done quickly.
2.16 Run-Length Encoding
Run-Length Encoding (RLE) compresses sequences by replacing consecutive equal values with a pair `(value, count)`.
2.15 Frequency Tables
A frequency table records how many times each value appears in an array, string, or stream.
2.14 Anagrams
Anagrams are strings or sequences that contain the same elements with the same multiplicities, possibly in different order.
2.13 Palindromes
A palindrome is a sequence that reads the same forward and backward.
2.12 Substring Search
Substring search locates occurrences of a pattern `p` inside a text `s`.
2.11 Tokenization
Tokenization converts a string into a sequence of meaningful units called tokens.
2.10 String Scanning
String scanning is the basic operation behind parsing, tokenization, validation, search, and text normalization.
2.9 Deduplication
Deduplication removes repeated values while preserving a chosen notion of identity and, optionally, order.
2.8 In-Place Modification
In-place modification changes an array without allocating another array of the same size.
2.7 Rotation
Array rotation moves elements by a fixed offset while preserving their relative circular order.
2.6 Partitioning
Partitioning rearranges an array so that elements are grouped by a predicate.
2.5 Sliding Windows
Sliding windows maintain a contiguous subarray `[l, r)` while both endpoints move forward.
2.4 Two Pointers
The two pointers technique uses two indices that move through an array or string in a controlled way.
2.3 Difference Arrays
A difference array is the inverse pattern of a prefix sum.
2.2 Prefix Sums
Prefix sums are a preprocessing technique for answering repeated range sum queries on an array.
2.1 Array Traversal
Array traversal is the base operation for all algorithms over linear data.
Chapter 2. Arrays and Strings
This chapter studies linear data as the primary substrate for algorithm design.