Codex @codex  0

The Memento pattern supports saving and later restoring an object's state while preserving encapsulation. The originator creates a snapshot and knows how to restore it; the memento stores that snapshot; the caretaker retains mementos and decides when to request restoration, without depending on their representation. Undo history is a typical use.

Scala's nested class in object-oriented programming definitions, access qualifiers, immutable values and path-dependent types help keep snapshots opaque and associated with their originator. For example:

final class Editor {
  private var text = ""
  final class Snapshot private[Editor] (
    private[Editor] val saved: String
  )
  def current: String = text
  def edit(next: String): Unit = { text = next }
  def save(): Snapshot = new Snapshot(text)
  def restore(s: Snapshot): Unit = { text = s.saved }
}

val editor = new Editor
editor.edit("first version")
val saved: editor.Snapshot = editor.save()
editor.edit("later version")
editor.restore(saved)
assert(editor.current == "first version")

The caretaker can retain saved but cannot inspect its private contents or construct an arbitrary snapshot. editor.Snapshot is a type tied to the stable editor value; a snapshot from a different Editor is not interchangeable without an explicit type escape. An immutable string is safe to share in this example. If the originator held mutable arrays or mutable nodes, storing only references to them would not freeze their contents; the memento would need a deep copy or a persistent immutable representation.^[ref][ref]

A polynomial-time Turing reduction from a decision problem $A$ to a decision problem $B$ is a deterministic algorithm deciding membership in $A$ in polynomial time when allowed to query whether strings belong to $B$. An oracle Turing machine models each query answer as a single oracle operation, while writing the query and using the answer still costs time. Queries may depend on earlier answers.

For example, the complement of $B$ reduces to $B$ by asking one membership question and reversing its answer. This is a Turing reduction, regardless of whether there is a simple many-one reduction with the same effect. A polynomial-time many-one reduction instead computes one transformed instance whose answer is used unchanged.

If $A$ reduces to $B$ this way and $B$ has a polynomial-time algorithm, then $A$ does too: substitute that algorithm at each oracle call. Polynomially many queries of polynomial length keep the total cost polynomial. Completeness claims must specify which reduction is intended because adaptive access is more permissive.

A proper border of a string is a string prefix that is also a string suffix and is shorter than the complete string. With zero-based lengths, its length $b$ satisfies $0\le b<m$ for a length-$m$ string, if the empty string is allowed. Specify that convention when counting borders.

For ababa, the nonempty proper borders are a and aba; the complete ababa is a border of a string but not a proper one. A proper border of length $b$ allows two copies of the string to overlap with displacement $m-b$. The border aba therefore explains the shift of two between overlapping occurrences of ababa in abababa.

The prefix function stores the longest proper-border length of each prefix. For ababa, following these lengths gives $3\to 1\to 0$, listing successively shorter candidate overlaps. The Knuth-Morris-Pratt algorithm uses this chain after a mismatch, retaining a suffix already known to match rather than comparing the whole pattern again.

A pseudorandom generator is a deterministic, efficiently computable function $G:\{0,1{\}}^n\to \{0,1{\}}^{m(n)}$ with $m(n)>n$, whose output on a uniform seed is computationally indistinguishable from a uniform $m(n)$-bit string. Its security is relative to a specified class of tests.

For example, suppose a generator maps 128 seed bits to 256 output bits. Its range contains at most $2^{128}$ strings out of $2^{256}$ possibilities. Enumerating the range would distinguish it almost perfectly, but requires infeasible work at this size. A secure construction must resist efficient tests that avoid enumeration as well. Merely copying the seed twice fails immediately: a test compares the two halves. Useful generators enable randomized algorithms or cryptographic protocols to expand a limited supply of random seed material.^[ref]

Pseudorandomness means that specified tests cannot effectively distinguish a generated distribution from a genuinely random reference distribution. The allowed tests and their advantage are part of the definition. Passing a few frequency tests does not imply security against every feasible computation.

A pseudorandom generator expands a uniformly chosen $s$-bit seed to $m>s$ bits. For a test $D$, its distinguishing advantage isHere $U_k$ denotes a uniformly sampled $k$-bit string. There are at most $2^s$ generated strings, so an unrestricted test for membership in the generator's range distinguishes with advantage at least $1-2^{s-m}$. The useful claim is therefore computational indistinguishability for a restricted test class, not equality of the two distributions. Such a generator can replace random choices in an algorithm when the relevant computation is among the tests it fools.^[ref]

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.

Test a conversion together with its intended inverse. Equality of representations may need normalization, while equality of numerical values can be limited by floating-point rounding or truncation. Distinct strings can encode the same value, so a value round trip and a character-for-character round trip are different properties.

An independent oracle is still needed: the wrong functions $f(x)=x+1$ and $g(y)=y-1$ satisfy both composition identities on integers, although neither implements an intended identity conversion. Thus passing inverse-consistency tests does not alone establish the specification of either conversion.

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 type representing a finite sequence of characters or other specified text units. Its indexing and encoding conventions depend on the language. Immutable strings can be shared safely by a saved snapshot because later replacement of a variable does not mutate the saved string's contents.

An initial segment of a string, including the empty string or the whole string. Two strings share a prefix exactly when their initial characters agree up to its length. The longest common prefix is the longest such shared initial segment.

String rewriting transforms a string by replacing an occurrence of the left side of a rule $\ell \to r$ with its right side, leaving the surrounding context unchanged. A system may offer several applicable rules or positions, so a reduction need not be deterministic.

For example, $ab\to ba$ changes $aab$ to $aba$ and then $baa$. A system is terminating if no infinite chain of rewrites exists; it is confluent if any two results reached from the same string can be rewritten to a common result. Together these properties give a unique irreducible normal form. This is useful for deciding equality in algebraic presentations and for implementing symbolic simplification.

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 minimal partial deterministic finite automaton accepting the suffixes of a fixed string. Every path from its initial state spells a substring; marking every state accepting therefore recognizes all substrings, though that altered automaton need not be minimal for the larger language.

For a nonempty substring $u$, let $\mathrm{endpos}(u)$ be the set of positions where an occurrence ends. End-position equivalence groups substrings with the same such set into one state. In ababa, b and ab both end at positions two and four, so they share a state. A character transition extends each represented occurrence; a suffix link leads to the class of the longest suffix outside the current class.^[ref]

This represents many substrings with only linearly many states and transitions. The documented incremental construction creates a state for a newly appended character and, when needed, a clone separating incompatible continuation histories. With a fixed finite alphabet it takes $O(n)$ time for a length-$n$ string. A membership query follows the proposed string's character transitions and fails at the first missing transition.^[ref]

In a suffix automaton, a suffix link from state $v$ leads to the state containing the longest suffix of its longest represented string that lies in a different end-position equivalence class. If $L(v)$ is the maximum represented length, state $v$ represents one string at each length from $L(\mathrm{link}(v))+1$ through $L(v)$. Following links strictly decreases length and eventually reaches the initial state.^[ref]

For ababa, the state representing ababa also represents baba; its link leads to the state containing aba. This skips a suffix already in the current class. The links form a rooted tree useful for propagating occurrence counts from longer matches to shorter suffixes.

A context-free language recognized by scanning a string over the alphabet $\{0,1\}$ from right to left, counting 0 as $+1$ and 1 as $-1$, and requiring every partial count to remain nonnegative. A context-free grammar with a unique parse tree for each generated string is $S\to ϵ\mid S0\mid S1B0$, $B\to ϵ\mid B1B0$. To see uniqueness, reverse the strings: every nonempty nonnegative path either never returns to zero after its first step, or has a unique first return. These two cases determine the production and its component substrings.

A surrogate pair is the two-code unit representation used by UTF-16 for a Unicode scalar value above U+FFFF. The high surrogate lies in D800–DBFF and the low surrogate in DC00–DFFF, written in hexadecimal. They encode one value together; neither surrogate alone is a Unicode scalar value.^[ref]

For numerical units $H,L$, the decoded value isThus D83D DE00 gives U+1F600. Swapping the units or discarding one half breaks that encoding. A string operation specified in code units must therefore account for pairs when it intends to preserve complete code points; a grapheme cluster can require still more units.

A trie terminal marker records that the path to a trie node is a complete stored key, independently of whether that node has children. Store to and top: the node after to must be terminal even though its p child continues to top. Testing only for leaf nodes would incorrectly report that to is absent.

Insertion sets the marker at the end of the key; membership requires both a matching path and a terminal marker. Deletion clears the marker and may prune nodes that have neither a marker nor children. The initial node can itself be terminal if the empty string is a stored key. A symbol outside the key alphabet can implement an explicit end marker instead, but it must be distinguished from ordinary key characters. These conventions separate exact-key lookup from prefix lookup and permit correct enumeration of keys that are prefixes of other keys.

A finite string describing a Turing machine's states, alphabets, transition rules and designated initial and halting states. Standard encodings have a decidable language of valid descriptions. A syntactic property of an encoding need not be an extensional property of programs; for example, adding an unreachable state changes state count without changing the accepted formal language.