The Setting
The shortest common superstring problem asks for a word of minimum length that contains every input word as a contiguous substring. The input words may overlap in the output. The objective counts symbols, although a symbol itself may require several bits to describe.
A symbol is a finite binary string, so the symbol alphabet is .✦ A word is a finite sequence of symbols, and is its symbol length.✦ An instance is a finite list of words; repetitions and empty words are allowed.✦ The input alphabet consists of the symbols appearing in these words.✦
A substring of a word is a word for which for some words and , either of which may be empty. Write for this relation. The set of common superstrings of is defined by (1). (1)✦ The optimum is the minimum symbol length in (2); the minimization ranges over all words in . (2)✦
The substring graph has as vertices the empty word and all distinct substrings of the input words.✦
The maximal input words are the distinct nonempty input words that are not proper substrings of another input word.✦
The distinct substrings of a word include the empty word and all words obtained by taking a prefix after deleting an initial segment.✦
The Bit-machine Model
For a finite list and a map from its entries to binary strings, the list representation is the binary string in (3). Juxtaposition denotes concatenation, and and denote single bits. (3)✦ Starting with the identity map on single bits, the symbol, word and instance representations , and are the successive applications of (4). (4) The input bit length and the total input symbol length are the distinct quantities in (5). (5)
A function from instances to words has a polynomial bit-machine implementation, denoted , if a deterministic Turing machine computes from in time bounded by a polynomial in , with a finite alphabet on every machine stack.✦ The machine and its polynomial bound are fixed independently of .
A bit stack store on a set of stack names assigns each stack a finite sequence of bits, with the first bit at the top.✦
For a set of private stack names, the public and private stacks comprise two public stacks indexed by zero and one and one private stack for each member of .✦
A bit stack program on stacks named by is built from pushing a bit, popping a stack, doing nothing, branching according to whether a stack is empty or starts with zero or one, sequential composition, and loops that repeat a body while a designated stack is nonempty.✦
An execution with instruction count records a bit stack program, its initial and final stores and its primitive instruction count; a push, pop or do-nothing instruction costs one, and a push or pop changes only its designated stack.✦ A branch costs one plus its selected execution, sequential composition adds the two execution counts, an empty loop costs one, and a nonempty loop costs one plus the body and remaining loop counts.✦
A linearly parsable encoding of values in a set is an injective binary encoding that admits a linear prefix scanner.✦
A linear prefix scanner for an encoding is a fixed bit stack program with a constant that, for every value , suffix and accumulator, consumes the initial code from one public stack and prepends its reversal to the accumulator on the other, leaving the suffix untouched.✦ It uses at most instructions and has empty private stacks before and after the scan.✦
For an update , a value with a linearly parsable encoding and a bound , the space bounded update replaces by when the encoding length of is at most and retains otherwise; it retains the same bound .✦
Write for the executable superstring algorithm fixed by the library.
A substring graph walk is a finite list of words recording its successive visited vertices.✦
The substring graph adjacency test accepts a pair of words precisely when the second is obtained from the first by appending one symbol or deleting its first symbol.✦
The graph walk validity test accepts a nonempty walk precisely when every visited word is allowed and every consecutive pair passes the adjacency test.✦
The appending edge count of a walk is the number of consecutive pairs in which the symbol length increases; in a valid walk, an up step appends one symbol and costs one, and a down step deletes the first symbol and costs zero.✦
For words and , the appended edge symbol is the one-symbol word consisting of the last symbol of when , and the empty word otherwise.✦
The walk output word consists precisely of the symbols appended on up steps, in traversal order.✦
The successive symbol appending walk from a word with appended word visits followed by every prefix of , in increasing prefix length.✦
The successive symbol deletion walk for words and visits the words obtained from by deleting zero through initial symbols.✦
The concatenation of walks and is followed by with its first vertex omitted.✦
A rooted tour is a walk starting and ending at the empty word; rooted tour concatenation joins a list of such tours in order, starting with the tour consisting only of the empty word.✦
The rooted word excursion of appends its symbols successively from the empty word and then deletes its first symbols successively back to the empty word.✦
The cyclic rotation of a walk at index concatenates its suffix starting at with its prefix ending at , omitting the repeated junction vertex.✦
Tour splicing inserts a cyclic rotation of into at their first shared vertex in , choosing the first occurrence of that vertex in ; an unsuccessful search uses index zero.✦
Tour insertion of into at index concatenates the prefix of through , then , then the suffix of starting at , omitting the repeated junction vertices.✦
Successive tour splicing inserts a list of tours into a walk from left to right.✦
Rooting a tour at a vertex appends from the empty word, traverses the tour cyclically from that vertex, and deletes back to the empty word; an absent vertex index uses the empty word.✦
Rooting a tour at a short word with bound roots it at the first visited word of length at most , using index zero if there is none.✦
The isolated symbol excursion of starts at the empty word and appends and deletes each symbol of separately.✦
The rooted walk test accepts a valid walk precisely when its first and last vertices are the empty word.✦
The computed word multiplicities come from a table initially zero on every graph vertex, updated simultaneously one more time than the maximum vertex length, with every update subject to the initial counting workspace bound.✦
The counting iteration bound uses maximum zero when the vertex list is empty.
For a multiplicity table , the left extension multiplicity of is the sum of over input symbols , with extensions outside the graph contributing zero.✦
For a multiplicity table , the right extension multiplicity of is the sum of over input symbols , with extensions outside the graph contributing zero.✦
Fix a default symbol; the candidate periodic text generated by a word with period parameter takes its symbol at integer coordinate from position modulo in , using that symbol for an absent position.✦
The periodic prefix test accepts a word when each of its symbols agrees with the corresponding position of the candidate periodic text.✦
A blocking occurrence of in at position has a nonempty part of on each side, every interior symbol of agrees with the candidate periodic text aligned at , and both endpoint symbols disagree with that alignment.✦
The blocking occurrence count is the number of starting positions satisfying the blocking occurrence test; overlapping occurrences are counted separately.✦
The weighted blocking count , with denoting the substring graph vertex set in this notation, is the sum over graph words of the number of blocking occurrences of in times .✦
For positive integers and , a nonempty word and a graph word with , the periodic multiplicity constraint is if both words match the candidate periodic text generated by with parameter and ; otherwise it is zero.✦
The constraints from one word take the maximum periodic multiplicity constraint over parameters and from zero through .✦
The maximum periodic constraint for is the maximum of its constraints from all graph words, with zero included.✦
The word multiplicity update is zero for the empty word and for words outside the graph; otherwise it is the maximum of the indicator that the word is a maximal input word, the left and right extension multiplicities, and the maximum periodic constraint.✦
A multiplicity table update replaces every graph word count by its word multiplicity update, calculating all new values from the old table.✦
The downward edge multiplicity is the computed count minus its right extension multiplicity, with subtraction truncated at zero.✦
The downward edge word list repeats each graph vertex exactly times.✦
An indexed word token consists of a natural-number identifier and a word✦; the suffix matching requests retain the identifiers of the indexed downward edge words and delete the first symbol of each word.✦
The indexed word tokens of a word list pair each word with its position in the list, starting at zero, so equal words at different positions have different identifiers.✦
A greedy prefix matching update chooses the first longest outstanding request, matches it to the first available token whose word extends its prefix, removes every copy of each selected token from its corresponding list, and prepends their pair to the matching; an empty request list is unchanged and an absent extension uses the empty word with identifier zero.✦
Greedy prefix matching starts with request tokens, available tokens and no pairs, and applies the matching update once for every initial request.✦
When no request is available, the longest available request is the empty word with identifier zero.
The computed prefix matching greedily matches the suffix matching requests to the indexed downward edge words.✦
The computed permutation edges connect the identifiers of the two tokens in each computed matching pair.✦
A thread representation consists of a list of words and permutation edges connecting their indices.✦
For a list of permutation edges and an index , the permutation successor is the second coordinate of the first edge whose first coordinate is , or zero if there is no such edge.✦
The computed thread representation uses the downward edge word list and its computed permutation edges.✦
For a thread representation with words, the periodic signature at an index is the sequence of first symbols encountered in successive permutation steps, using the default symbol when the indexed word is absent or empty.✦
Two thread indices pass the compatibility test when some permutation step count below the word count takes the first to an index with the same periodic signature as the second.✦
The representative of a thread index is the least compatible index below the word count, with zero as the fallback.✦
The thread group representatives are the indices equal to their own least compatible thread index.✦
The aligned thread indices of a group are the indices whose periodic signatures equal that of the group index.✦
The thread signature period is the least positive step count at most the word count that returns to the same periodic signature, or zero if no such step exists.✦
The thread period word is the prefix of the periodic signature whose length is the thread signature period.✦
The ranked thread word length at phase and rank is the least threshold from zero through the encoding length of the thread representation for which more than aligned indices have word length at most that threshold after permutation steps, with zero as the fallback.✦
The ranked layer exit lengths list the ranked thread word lengths over all phases below the thread signature period.✦
A periodic layer is specified by a period word and a list of exit lengths indexed by phase✦; the thread group layer data consist of the thread period word and the ranked layer exit lengths for ranks below the number of aligned thread indices.✦
Periodic layer group data consist of a period word and one list of exit lengths for each layer.✦
A collection environment consists of layer group data, active group indices and a stride for indexing layers globally✦; the thread collection environment lists the layer data at every thread index, uses the thread group representatives as its active groups, and takes the word count as its layer indexing stride.✦
A collection context specifies allowed graph vertices, a collection environment and a bound for completion searches✦; the computed collection context uses the substring graph vertices, the collection environment obtained from the computed thread representation, and the counting iteration bound.✦
For an integer-indexed text and integer endpoints , the finite text window lists its symbols from through and is empty when .✦
An integer interval is specified by two integer endpoints and is interpreted as a half-open window.✦
The two-sided periodic text of a word takes its symbol at integer coordinate from position modulo in , using the default symbol when absent.✦
A periodic text window of on is the word read from its two-sided periodic text at those coordinates, and is empty when .✦
The cyclic word shift of by displacement is its periodic text window of length starting at .✦
For period words and an integer displacement , the periodic text inequality test compares the window of starting at zero with the window of starting at displacement , both of length , and accepts precisely when they differ.✦
For a list of exit lengths, the periodic exit coordinate at integer position is plus the exit length indexed by modulo the length of , using zero for an absent entry.✦
The preceding exit coordinate at is the periodic exit coordinate at .✦
At phase , let be the preceding exit coordinate and the current exit coordinate; the layer contents at that phase are the periodic text windows starting at and ending at , for offsets from zero through the nonnegative part of .✦
The periodic layer contents concatenate the layer contents at all phases below the period word length.✦
The short layer words are the words in the periodic layer contents whose symbol lengths do not exceed the period word length.✦
The one-period layer tour starts at phase zero and follows successive single-position passages for as many positions as the period word length, appending to each current exit and deleting the first symbol to advance the start, using the layer exit lengths.✦
Selected layer saturation successively splices the one-period tours of the selected layers into a walk, using empty exit lengths for an absent layer.✦
Complete layer saturation successively splices the one-period layer tours of all listed layers into a walk.✦
The saturated rooted word tour of saturates its rooted word excursion with the selected layers.✦
For the short word layer tour, saturate the rooted excursion of the first short layer word with that layer, using the empty word when there is no short layer word.✦
Saturating the rooted excursion of the periodic text window from the specified phase to the preceding exit of the upper boundary layer with the selected layers gives the rooted upper layer tour.✦
For lower and upper exit functions , phase , period and displacement multiplier , put and ; the geometric band walk stays at when , and otherwise appends to and connects to the base window translated by .✦
For the saturated band walk, use the exit functions of the two boundary layers and the period word length to saturate the geometric band walk with the selected layers.✦
The geometric collective walk from first appends to the larger of and the upper exit immediately before , then connects to .✦
The saturated collective walk is obtained from the geometric collective walk by saturation with the selected layers; this uses the upper boundary exit function and a translation of one period for each selected layer.✦
For an exit function , the geometric individual walk sets to the larger of and , connects to and appends from to .✦
Saturating the geometric individual walk with its single selected layer gives the saturated individual walk, using that layer’s exit function and the period word length.✦
For an initial window , an upper exit function , phase , period and layer count , the geometric short sweep puts , takes to be the smaller of and , sets , deletes to start , appends to stop and connects to .✦
For the saturated short sweep, apply saturation to the geometric short sweep with the selected layers, using the upper boundary exit function and a translation of one period for each selected layer.✦
Layer band attachment splices the saturated band walk into the current walk, with displacement multiplier equal to the selected layer count.✦
The window prefix deletion walk successively deletes the window from the front of , retaining .✦
The window suffix appending walk starts at and successively appends the symbols of .✦
The window connection walk from endpoints to first deletes to start and appends to stop when ; otherwise it deletes to the empty window at , makes the isolated symbol excursion on , and appends .✦
Successive window connections start at the specified initial window and concatenate the connection walks through the remaining windows in list order, omitting their repeated initial vertices.✦
Endpoint sum ordering stably orders a list of integer intervals by the sum of their endpoints.✦
Ordered window traversal connects the initial window through the list of windows in endpoint sum order and then to the specified final window.✦
For an integer translation , the host window excursion appends from the base window to stop , traverses the requested windows in endpoint sum order, and connects the last window to , using as the last window when the list is empty.✦
For an integer displacement , the shifted window attachment connects to and then to .✦
For an exit function , the single-position passage at appends from the preceding exit to while keeping start , and then deletes the first symbol to advance the start to .✦
For an initial position and a nonnegative step count , the periodic segment walk starts at and concatenates the single-position passages at , omitting repeated junction vertices.✦
An overlap record consists of an integer alignment displacement and integer start and stop coordinates.✦
An overlap record with displacement and interval is valid for period words and target exit function when , , and the periodic text windows of on and on agree.✦
For displacement bound , phase and search bound , the bounded overlap record candidates have displacement from zero through , start for , and stop for .✦
The lexicographically greatest rotation phase is the first phase below whose full-length periodic text window is at least every other such rotation, using zero if there is none.✦
A layer catalogue is a list of layers, each specified by a period word and its exit lengths.✦
Upper completion parameters consist of a selected layer count, a target catalogue index and an overlap record.✦
For layer count and cutoff , the upper layer indices are , with none when .✦
The upper completion candidates list every selected count from zero through the layer bound, each specified target index, and every bounded overlap record for that target, using the target word length as the displacement bound.✦
The foreign periodic text test accepts when the group period word and the selected target word pass the periodic text inequality test at the recorded displacement.✦
For layers of period , cutoff , phase , selected count and record , the upper completion admissibility test requires , a valid overlap record, , top preceding exit at most , and top preceding exit minus the exit at of layer at most .✦ It also requires every upper layer below to have preceding exit at at most .✦
Admissible upper completion selection takes the first candidate satisfying both the upper completion admissibility test and the specified foreign predicate, using zero for every parameter if there is none.✦
A closure block specifies source and target identifiers, layer indices, an overlap word, a period, a cost reserve, an internal walk and candidate linking walks.✦
A block closing action specifies a list of blocks to remove and a proposed replacement walk.✦
A closure state consists of the current walk and the remaining closure blocks.✦
Closure block assembly shifts selected layer indices by the given offset, takes the overlap word from the periodic text window, and assigns a block of layers of period a reserve of .✦
An individual closure block uses the one-period tour of its single layer internally and its saturated individual walk as its sole linking walk.✦
A collective closure block uses the saturated band walk with displacement multiplier one less than its selected layer count internally, and offers the saturated collective walk and saturated short sweep as linking walks.✦
The layer coverage test accepts a walk when it visits every word in the contents of each specified layer, treating an absent layer as empty.✦
A closure action is admissible when its new walk is rooted and valid, its cost is at most the current cost plus the reserves of the removed blocks, it retains every old visited word, and it covers all layers of each removed block.✦
The single-block actions remove one block and either concatenate its internal walk rooted at a word no longer than its period or splice one of its linking walks into the current tour.✦
A paired-block action removes two blocks, splices the second block’s internal walk into a linking walk of the first, roots the result at a word no longer than the second period, and concatenates it to the current tour.✦
The closure action candidates list each single-block action and each paired-block action for distinct blocks.✦
Admissible closure selection takes the first admissible candidate, or removes no blocks and keeps the current walk if there is none.✦
The block closure update replaces the current walk by the selected action’s walk and removes its selected blocks from the remaining list.✦
The block closure tour is the walk left after one block closure update per initial block, with every update subject to the initial closure workspace bound.✦
A layer distribution result consists of a walk, a list of closure blocks and a list of layer indices to transfer.✦
Single-layer distribution uses a short word layer tour when the layer has a short word; otherwise it creates an individual closure block when the overlap stop is at most the layer exit at the overlap start plus the period, and leaves the layer for transfer in the remaining case.✦ The last two cases use the tour consisting only of the empty word.✦
Multiple-layer distribution applies single-layer distribution to every selected layer, concatenates their rooted tours, and concatenates their block and transfer lists.✦
Overlap record distribution takes the selected layers at or above the lower boundary as a collective block when the overlap stop is at most the lower boundary exit at the overlap start plus their number times the period, distributing the lower selected layers individually.✦ Otherwise it distributes all selected layers individually.✦
With layer indexing stride , the global layer indices list the numbers for each active group and each local layer index below the number of layers in that group.✦
A collection plan consists of a walk, closure blocks and layer transfer requests✦, each of which specifies a source group, a target layer, source layer indices and an overlap record.✦
The reserve of a layer transfer request for source layers of period is .✦
A scheduler state consists of the unprocessed group indices and the current collection plan.✦
The group cost allowance for layers of period is .✦
The collection plan budget is its walk’s appending edge count plus all its block reserves and request reserves.✦
The remaining collection budget is the current plan budget plus the cost allowances of all unprocessed groups.✦
The canonical group phase is the lexicographically greatest rotation phase of its period word.✦
Minimum-period group selection chooses the first remaining group whose period is no larger than every other remaining group period, using zero if the list is empty.✦
The initial collection state has every active group unprocessed, the tour consisting only of the empty word, and no blocks or requests.✦
The incoming group requests are precisely the requests whose target layer belongs to that group.✦
The global layer catalogue lists the period word and exit lengths at each global index below the number of group data entries times the indexing stride.✦
The global layer contents list the periodic layer contents of every layer in the global catalogue.✦
A host overlap entry consists of a source identifier, a period word, overlap start and stop coordinates, and a required coverage endpoint, all coordinates being integers.✦
Shifting a host entry by an integer displacement cyclically shifts its period word, adds the displacement to its three coordinates and retains its source identifier.✦
Request attachment data consist of a period word, a source window and an attachment window.✦
For host period , base entry and source entry , the entry attachment data use the period word of and its window from the overlap start to the coverage endpoint.✦ The attachment window starts at the smaller of the source start plus its period word length and the base start plus , and stops at the larger of the source coverage endpoint and the base stop.✦
The periodic request attachment is the shifted window attachment in the periodic text of its request period word, using that word’s length as the period and the two request windows.✦
For period and intervals and , first choose the displacement taking to plus the nonnegative remainder of modulo ; the periodic normalization displacement is this displacement if it moves to at least , and one period more otherwise.✦
Entry periodic normalization shifts an entry by the periodic normalization displacement determined by its overlap interval and the base overlap interval.✦
The other source entries relative to a base entry are the entries whose source identifiers differ from its source identifier.✦
The rooted host excursion constructs the host window excursion in the host word’s periodic text, successively splices the periodic request attachments into it and roots the result at the first word within the specified length bound.✦
The normalized host tour uses the base entry’s overlap interval and coverage endpoint for the rooted host excursion, takes the base period word length as its rooting bound and obtains attachment data from the other source entries.✦
The normalized request tour first normalizes every entry relative to the chosen base with period equal to the host word length, then forms the normalized host tour.✦
The host request tour candidates take each host entry in turn as the base of a normalized request tour.✦
The saturated host tour candidates apply complete layer saturation to every host request tour candidate, including the host layer and all requested layers.✦
A request host entry carries the source group identifier, the source period word shifted by the recorded displacement, the displaced overlap endpoints and the source layer’s preceding exit at the overlap start shifted by that displacement.✦
A recipient tour is admissible when it is rooted and valid, covers the recipient layer and every requested source layer, and costs at most twice the recipient group period plus the sum of the request reserves.✦
The recipient tour candidates are the saturated host tour candidates for the target layer, with the host entries and layer data obtained from its requests.✦
Recipient tour selection takes the first admissible recipient tour candidate, using the default walk if there is none.✦
The recipient layer indices of a group are its local layer indices with at least one request targeting that layer.✦
The incoming request tour concatenates the selected rooted recipient tours for the recipient layers, using at each layer exactly the requests targeting it.✦
Hard-case distribution distributes the upper layers according to the selected overlap record, with lower boundary equal to the layer count minus the selected count and upper boundary equal to the top layer, using the canonical group phase.✦
The hard-case collection plan keeps the distributed tour and blocks and creates one transfer request for the unassigned layers if there are any.✦
Upper layer completion keeps the current tour when no upper layers remain; otherwise it uses a rooted upper layer tour when the top preceding exit minus the phase is at most the number of upper layers times the period.✦ If that fails, it attaches a layer band when the cutoff is positive and the top preceding exit minus the exit at the phase of the layer below the cutoff satisfies the same bound; in the remaining case it selects admissible foreign completion parameters and concatenates the resulting hard-case plan.✦
Lower layer preparation begins with the tour assembled from incoming requests and returns cutoff zero if no layer receives a request.✦ Otherwise it takes the largest index of a layer receiving a request, uses the first request there to attach the layers through that index that receive no request along its displaced overlap interval, and returns the cutoff immediately above that recipient.✦
The group collection plan applies upper layer completion to the cutoff and tour returned by lower layer preparation.✦
The group processing update leaves the scheduler state unchanged when no unprocessed group remains.✦ Otherwise it chooses the first remaining group of minimum period, forms its collection plan from its incoming requests, removes that group from the unprocessed list, concatenates the new tour, appends the new blocks and replaces the incoming requests by the new requests, retaining the other pending requests.✦
The group collection sweep starts from the initial collection state and performs one group processing update per active group, each subject to the initial scheduler workspace bound.✦
The completed collection tour applies block closure to the group collection sweep, using its accumulated tour and blocks, the allowed vertices and the global layer contents.✦
The requests at one layer are precisely the pending requests whose target is that layer.✦
The unprocessed group requests retain the requests whose target layer belongs to a different group.✦
Host entry expansion lists a request host entry for every source layer in every request.✦
The requested layer data list the catalogue layers at every source layer index specified by the requests.✦
The Claim
Theorem 1. There is a deterministic algorithm from instances to words with the properties in (6). (6)✦ For the fixed algorithm and every finite instance , the output satisfies (7). (7)✦ The implementation property of this same algorithm is (8). (8)✦
What Is Checked
The claims range over finite lists of words with arbitrary finite binary strings as symbols, using contiguous substring containment, the unrestricted optimum and the specified binary input and output representations.