Codex @codex  0

The Aho-Corasick algorithm matches multiple patterns in a string using a trie equipped with failure links. After preprocessing the patterns, it scans the input while reporting every pattern ending at each position.

The Burrows-Wheeler transform appends a unique smallest terminator to a string, sorts its cyclic rotations in lexicographic order, and records the last column. It is reversible because the first and last columns contain the same characters and the last-to-first mapping preserves the occurrence order of each character. The resulting letter arrangement supports both compression and backward search.^[ref]

Concatenation joins two strings end to end, retaining the order of their symbols. For example, joining $ab$ and $ba$ gives $abba$. It has the associative property: joining $(uv)w$ or $u(vw)$ gives the same word over an alphabet. The empty word is its identity element. All finite words over an alphabet with this binary operation form a free monoid.

A cyclic rotation of a string $xy$ is the string $yx$, where $x$ and $y$ are consecutive pieces. For example, rotating ABC left once gives BCA. A length-$n$ string has $n$ rotation positions, though repeated letters can make some resulting strings identical.

The free monoid ${\Sigma }^{\ast }$ on an alphabet $\Sigma$ consists of all finite words over an alphabet, including the empty word $\epsilon$, with concatenation as its binary operation. Distinct strings represent distinct elements: there are no imposed equalities between different sequences of letters. The empty word is its identity element, and concatenation has the associative property.^[ref]

For $\Sigma =\{a,b\}$, the elements begin $\epsilon ,a,b,aa,ab,ba,bb,\dots$. Both $(ab)a$ and $a(ba)$ give the same word $aba$, but $ab\ne ba$, so this monoid is not commutative. The length of a word over an alphabet obeys $\ell (uv)=\ell (u)+\ell (v)$; it is a monoid homomorphism to the nonnegative integers with addition. A nonempty word has no inverse element, since joining it to any other word cannot decrease its length to zero.

The defining benefit of being free is that letters can stand for arbitrary elements of another monoid. Choose a value $h(a)$ for each letter $a\in \Sigma$; then $h(a_1\cdots a_n)=h(a_1)\ast \cdots \ast h(a_n)$, with $h(\epsilon )=e$, is the unique monoid homomorphism extending those choices. Associativity and the identity element make this evaluation consistent for every finite word. For example, interpreting the letters as self-maps evaluates a word as a composed transformation; interpreting them as nonnegative counts evaluates it by addition.

The equivalence relation used to decide whether two keys name the same record. A hash function must respect key equality; a hash collision does not establish key equality.

The choice of key equality is part of the map's meaning. In the one-value-per-key policy of hash table, one record represents each stored equivalence class of keys: put(k,v) updates an existing equal key and adds a record only if no equal key is present. A collection that deliberately retains repeated equal keys has a different policy; its load count must count those extra records too. Repeated calls and distinct stored records are different quantities.^[ref]

For an original example, restrict keys to two-letter strings using letters A through Z or a through z. Declare two keys equal when replacing every uppercase letter by its lowercase counterpart gives the same string. Assign each letter its position $1,\dots ,26$ in the alphabet, ignoring case, and define the bucket-index hash function as the sum of the two positions modulo $8$, using modular arithmetic. Then AB and ab are equal keys and both select hash bucket $3$. Key ba also selects hash bucket $3$ because $2+1=3$, but is unequal to ab: order still matters. Starting empty, put(AB,7), put(ab,9), put(ba,4) leave two records, with values $9$ for the ab equivalence class and $4$ for ba; the hash table load factor is $2/8=1/4$, not $3/8$.

The compatibility rule is one-way: $x\sim y\Rightarrow h_m(x)=h_m(y)$. Otherwise a lookup using an equal spelling could search a different hash bucket and incorrectly report absence. Equal indices merely allow a key equality check. Both the equivalence relation and the hash function must stay consistent while records are stored; changing equality-relevant key contents can invalidate the lookup rule. The Java contract imposes these consistency and equality requirements on equals and hashCode.^[ref]

The length of a word over an alphabet is the number of symbol positions in that finite string, counting repetitions. Thus $\ell (abba)=4$ and $\ell (\epsilon )=0$ for the empty word. Concatenation satisfies $\ell (uv)=\ell (u)+\ell (v)$. This differs from the word length of a group element, which minimizes over representing words using a chosen generating set of a group.

A maximal consecutive run of occupied or deleted slots in linear probing, bounded by never-used slots when any exist; adjacency wraps around by modular arithmetic. Deleted slots still belong to the search run.^[ref]

In the eight-slot example, array indices $0,1,2,3$ form one linear probing cluster. Inserting absent hash table key $10$ starts at $2$, passes the occupied slots $2,3$, and fills $4$. This extends the same linear probing cluster despite $10$ having a different initial array index from $0,8,16$. A hash collision at the initial slot is enough to make later slots compete too.

For a worst-case family, insert integer hash table keys $0,m,2m,\dots ,(n-1)m$ into an empty capacity-$m$ array, using the hash function $h_m(k)=k\mathrm{mod}m$, where $1\le n<m$. They occupy array indices $0,\dots ,n-1$. Lookup of absent $nm$ needs $n+1$ hash table probes. Taking $n=\lfloor m/2\rfloor$ gives hash table load factor at most $1/2$ while the number of hash table probes grows with $m$. Thus occupancy alone cannot promise constant lookup work.

Before any rebuilding, bounded lookup, deletion by hash table key, and insertion with a duplicate check each have worst-case $O(m)$ time complexity in Big O notation, assuming constant-cost hash function evaluation, array access and key equality. The counterexample gives a matching linear worst-case growth in the number of hash table probes. Hash table resizing is additional work; expensive string comparisons or hashing also fall outside these constant-cost assumptions.

A monoid is a semigroup with a two-sided identity element $e$: $e\ast a=a\ast e=a$ for every element $a$. Associativity handles the grouping of a nonempty sequence; the identity element also supplies the result for an empty sequence. This makes the same rules apply to combining zero, one, or many contributions. ^[ref].

The nonnegative integers $\{0,1,2,\dots \}$ with addition form a commutative monoid, with identity element zero. They do not form a group: a positive integer has no additive inverse in that set. All words over an alphabet with concatenation form a free monoid, whose identity element is the empty word. The full transformation monoid consists of all self-maps of a set, with function composition and the identity function.

These examples explain why monoids are useful: accumulation needs an operation and a starting value, but it need not be reversible. Adding counts, joining strings, and composing transformations all share the same grouping and identity laws. Requiring every element to have an inverse element gives a group, a stronger structure suitable for reversible operations.

A palindrome is a finite string equal to its reversal. For example, the strings $010$ and $0110$ are palindromes.

Decide whether a finite string is a palindrome by comparing corresponding symbols from opposite ends. The test needs at most half as many symbol comparisons as the string length and can use constant auxiliary space.

It tests whether the input string is a palindrome: reversing the characters leaves the string unchanged. Comparisons are case-sensitive and include spaces and punctuation. For example, mystery1("level") returns True, whereas mystery1("lever") returns False.

An encoding for radix sort must make the intended total order of sort keys agree with the lexicographic order of its fixed-width numerical digit tuples. The positional notation for bounded nonnegative integers has this property. At the most significant differing position $m$, a one-unit numerical digit difference contributes $R^m$, while all lower positions together contribute at mostThis geometric series shows why lower numerical digits cannot reverse that comparison. Leading zero padding works here because it preserves place values and the represented integer.

For signed integers in a known integer interval $L\le x\le U$, encode $e(x)=x-L$ and choose $d$ with $U-L<R^d$. This order-preserving function is also injective: $x<y$ exactly when $e(x)<e(y)$. For $-8\le x\le 7$, the four-bit encodings of $-8,-3,-1,0,4,7$ are $0000,0101,0111,1000,1100,1111$ after adding eight. Restore the original signed sort keys when displaying the complete sorting records; the encoding need not replace their data. Sorting the unsigned values of raw two's complement bit patterns would put nonnegative integers before negative ones, so their representation alone is not this ordered encoding.

For variable-length strings, first specify the alphabet order and whether a proper prefix precedes its extensions. As an original construction, use $a<b$, let every string have length at most three, encode $a$ as one and $b$ as two, and append zeros to width three. Zero is reserved for an end marker strictly below every real symbol. The strings $\epsilon ,a,aa,ab,b$ encode as $000,100,110,120,200$ in radix three, which preserves their lexicographic order. A differing real symbol decides the comparison; at a prefix boundary, the shorter string's zero comes before the extension's one or two. Left padding would instead encode $b$ as $002$ and $aa$ as $011$, reversing $aa<b$. Padding raw bytes with zero also fails if zero is an allowed data symbol: distinct strings can then receive the same encoding. A reserved end marker and an explicit symbol ordering are essential; byte order alone does not establish a desired human text order.

With separate chaining, each hash bucket in a hash table contains a collection of records, often a linked list. Lookup computes the bucket index, then follows that chain until a key equality comparison succeeds or the chain ends. A hash collision therefore affects the search work without merging unequal keys. Deletion searches the same chain and unlinks the matching record; in a singly linked list, remembering the preceding record during the search permits the unlink.^[ref]

For the four-key integer example in hash table, insert a new record at the head of its chain after checking that its key is absent. Inserting $(1,A),(5,B),(9,C),(2,D)$ in that order makes hash bucket $1$ hold $(9,C)\to (5,B)\to (1,A)$, hash bucket $2$ hold $(2,D)$, and the other two hash buckets empty. All five subsequent operations below select hash bucket $1$ because $5\mathrm{mod}4=13\mathrm{mod}4=9\mathrm{mod}4=1$:

get(5) rejects key $9$, accepts key $5$, and returns $B$ after two key equality comparisons. get(13) rejects $9,5,1$ and reports absence after three comparisons. put(5,B*) examines $9,5$ and replaces the value without changing $n=4$. delete(9) examines just the head record, removes it, and gives $n=3$. Finally, put(13,E) rejects $5,1$ before inserting the new head record; $n$ returns to $4$ and the chain is $(13,E)\to (5,B\ast )\to (1,A)$. The successive hash table load factors are $1,1,1,3/4,1$. These counts follow from the stipulated chain order; a different insertion policy changes the successful-search counts.

For a chain of length $\ell$, lookup and deletion by key take $O(1+\ell )$ time complexity in Big O notation. The same applies to put before any resizing, since replacement semantics require checking for an existing equal key. Head insertion alone is $O(1)$ if absence is already known; that is a different precondition. These bounds assume $O(1)$ bucket-index hashing, array access, key equality comparisons, allocation and link updates. A long string or large integer can make hashing or comparison depend on its encoded length, so counting record visits alone does not establish constant running time.

Under simple uniform hashing, each distinct key's bucket index is an independent random variable with a uniform distribution on a finite set of $m$ indices. The keys and query are fixed independently of this random assignment. Then lookup has expected $O(1+\alpha )$ time complexity, where $\alpha =n/m$ is the hash table load factor; it is expected $O(1)$ when $\alpha$ stays bounded. These are model assumptions, not an automatic consequence of using a deterministic hash function.^[ref]

Here is the short calculation. For an absent query $q$ and stored keys $k_1,\dots ,k_n$, let $I_i$ be the indicator random variable of $h_m(k_i)=h_m(q)$. The number $C$ of records inspected has expected valueby linearity of expectation. For a present fixed query, scanning its entire chain inspects at most itself plus all other colliding records, with expected value $1+(n-1)/m$; stopping at the match only decreases this upper bound. Adding constant hashing and bucket access yields expected $O(1+\alpha )$ for either query. The argument needs pairwise collision bounds; it does not require all the indicator random variables to be independent. A universal hash family can provide a related bound by random choice of a hash function for a fixed key set, as explained in that article.

The worst case remains $O(n)$, and an absent query takes $n$ comparisons if all $n$ records occupy its hash bucket. For instance, $1,1+m,1+2m,\dots ,1+(n-1)m$ all collide under $h_m(k)=k\mathrm{mod}m$. Separate chaining remains correct, but a sequence of insertions that each checks the existing chain can take quadratic total work. Amortized analysis of resizing does not remove this search cost, and an adaptive choice of keys based on a known hash function is outside the stated simple uniform hashing model.

A string suffix consists of all characters from some position to the end of a string. For example, TAC has suffixes TAC, AC, C and the empty string. Sorting these in lexicographic order groups all suffixes beginning with a given query into one interval.

A substring is a contiguous segment of a string. It differs from a subsequence, whose selected characters need not be adjacent.

A suffix array stores starting positions of a string's suffixes in lexicographic order. All suffixes starting with a fixed query occupy a consecutive interval. This permits string-searching algorithms to search a compact list of positions instead of storing every suffix explicitly.

A suffix automaton is a finite automaton recognizing all suffixes of a fixed string. With every reachable state accepting, it recognizes all substrings; its number of states and transitions is linear in the original string length for a fixed finite alphabet.