Longest Repeated Substring Problem¶

Find a longest contiguous factor that occurs at two distinct starts in one sequence, and return that factor.

Version: v1 · 2026-10-25 · History
Domain-specific #: 14412
Domain group: Applied Sciences & Engineering
Origin domain: Computer Science & Software Engineering
Subdomain: String Algorithms → Computer Science & Software Engineering
Aliases: Longest repeating substring problem

Core Idea¶

The longest repeated substring problem asks for a contiguous factor of one finite sequence that occurs at two different start positions and has maximum length among such factors. The symbols and their equality rule are fixed for that input. Occurrences may overlap: in banana, ana starts at zero-based positions 1 and 3 and is a longest repeated factor. A solver returns a maximizing factor value, not merely its length. It may also report occurrence positions. If several values tie, any one can be returned unless an interface specifies a tie rule; a no-repeat input needs an explicit empty or no-result convention. Dębowski defines the maximum with two different starts and permits overlap.^[1]

This is a problem specification. A suffix tree is one way to solve it: repeated factors appear as shared prefixes of suffixes, and a deepest internal node identifies a longest one.^[2] The data structure, a unique terminator, and a particular traversal are not part of what an answer must be. The required relation is one input, two equal contiguous occurrences, a global maximum, and the returned factor.

Structural Signature¶

Sig role-phrases:

Ordered input and equality rule. One finite sequence fixes which items count as symbols and when two symbols agree. It is constitutive. Without a stable rule, “the same factor” is undefined.
Distinct occurrence starts. The factor begins in two different places in that input. This is constitutive even when numeric offsets are not printed with the answer. Requiring disjoint intervals would change the problem; overlapping occurrences count.^[1]
Exact contiguous factor. The same uninterrupted symbol run occurs at both starts. This is constitutive. Allowing omissions or mismatches would change the admissible candidates.
Global length maximum. The selected factor is at least as long as every other qualifying repeat in the input. This is constitutive; a locally long or arbitrary repeat does not suffice.^[2]
Returned factor value. One maximizing run is identified as a sequence of symbols. The caller may also receive its length and locations. Returning only the optimum length omits the requested factor.

These five roles specify what is sought. They do not require a suffix tree, a particular alphabet, or a universal output convention for ties and inputs without a nonempty repeat.

What It Is Not¶

It is not longest common substring between two separately supplied sequences: both occurrences here belong to one input. It is not fixed-pattern matching: the factor to be returned is discovered rather than given in advance. It is not longest repeated subsequence: skipping intervening symbols breaks contiguity. It is also not merely the maximum-repeat-length statistic; a number can tell how long the optimum is without identifying the factor. Dębowski's analysis uses lengths for a statistical comparison, but its whole-text tables also print the maximizing strings.^[1]

Counting occurrences beyond two, forbidding overlap, or enumerating every repeated factor creates a related task with a changed answer set. Stanford presents an at-least-k occurrence version separately from the base problem.^[2] AdaCore's later search for all copy-pastes is likewise broader than its first longest-run pass.^[3]

Scope of Application¶

The specification can be applied to any declared ordered symbol sequence with exact equality. Two documented settings show how the same roles persist under different representations:

Source-code copy detection. AdaCore converts code features into an ordered sequence of hash codes and finds its longest repeated run.^[3] The returned duplicated span is mapped to source locations for inspection.^[3] Equality is under that representation; the result is a copy-paste candidate, not proof of byte-identical source.
Written-text repetition analysis. Dębowski searches cleaned literary texts as character or word sequences.^[1] For each whole text, the study computes a maximum and prints actual repeated strings in its tables; their lengths are then used to study repetition growth.^[1] The tables do not print paired numeric start offsets.

The same name can be used for genome or compression tasks, but those are not established as independent whole cases by the three sources used here. The symbol convention and the meaning assigned to a found factor must be checked in each setting.

Clarity¶

The problem separates what repeats, where it repeats, and how long the longest repeat is. ana is one factor value with two overlapping occurrences in banana; its length is 3, while 1 and 3 are witness positions. A length-only report is therefore a projection of the answer, and a position-only report requires a way to recover the factor value. A tie between distinct maximal values does not invalidate either value, but a reproducible interface should say which to return.

It also separates the exact factor relation from the way an input is represented. AdaCore's AST-derived hash sequence may treat different source spellings as equal code units.^[3] Dębowski's cleaned word sequence uses a different unit and preprocessing rule.^[1] In each case the equality used during the search must match the declared sequence, rather than an unstated claim about the raw source material.

Manages Complexity¶

There can be many candidate factors and many pairs of positions in a long input. The five-role specification reduces the question to a predicate on factors—two distinct exact occurrences—and an ordering by length. Suffixes organize all starts of a sequence; two suffixes sharing a prefix witness a repeated factor. A deepest qualifying internal node in a suffix tree compactly selects an optimum instead of examining every pair of visible substrings.^[2]

That compression is an algorithmic benefit, not an identity condition. Stanford's linear-time discussion depends on a suitable suffix-tree construction and its computational assumptions; it should not be read as an unconditional bound for every alphabet or every suffix-array implementation.^[2] An implementation also needs to decide whether its unit is a byte, character, word, token, or another symbol.

Abstract Reasoning¶

First fix the input sequence and equality convention. A proposed answer must then pass two tests: find distinct starts with equal contiguous runs of that value, and rule out every longer repeated factor. The suffix view supplies the latter test by comparing shared prefixes: if a deeper shared path exists, the proposed value was not globally longest.^[2]

This reasoning also exposes changes of task. If ana in banana is rejected solely because its occurrences overlap, a nonoverlap constraint has been added. If a detector returns only the number 3, it has solved the optimum-length projection but has not returned ana. If it reports many duplicated blocks, that output can contain a longest one without itself being the single-value optimization problem.

Knowledge Transfer¶

The five-role specification applies in both settings, while their actual computations differ. AdaCore finds a longest equal run in a code-derived sequence and maps it to source-code spans.^[3] Dębowski finds maximal repeated passages in literary texts and prints their values for statistical study.^[1] What does not transfer automatically is the equality rule or the interpretation of the result. An equal run of normalized code hashes is not necessarily byte-identical source.^[3] Dębowski notes quotation and document-preparation effects, so a long printed passage is not necessarily a meaningful literary motif.^[1]

The live Optimization Prime is a literal parent pattern: choose feasible alternatives under an objective and seek a declared optimum, regardless of the carrier. What does not transfer outside ordered sequences is the exact contiguous self-repeat condition. These two cases do not establish a new substrate-independent longest-repeat Prime.

Examples¶

Canonical: code-copy inspection¶

In AdaCore's first detector, code elements are reduced to a sequence of hash codes, then a suffix-tree search identifies a longest repeated run and returns source locations associated with duplicate code spans.^[3] A developer can inspect the reported locations as copy-paste candidates. The later extension that seeks all copy-pastes should not be substituted for this first longest-run example.

Mapped back: The hash-code run is the ordered input and equality rule; two offsets in that run are distinct occurrence starts; their equal adjacent hashes form the exact contiguous factor; the deepest shared path supplies the global length maximum; the mapped duplicate span supplies the returned factor value with locations. The source-code meaning is an interpretation layered on the representation-relative answer.

Applied: literary-text repetition study¶

Dębowski processes whole Gutenberg literary texts and tabulates maximal repeated substrings at character and word levels.^[1] Tables 1–3 print actual longest strings and lengths for the studied texts, while the paper examines how maximum length grows with text size.^[1] Its published whole-text tables do not identify both exact numerical positions for each printed string.

Mapped back: Each cleaned whole text is an ordered input and equality rule; the formal definition supplies distinct occurrence starts and admits overlap; identical uninterrupted character or word runs supply the exact contiguous factor; the whole-text maximum supplies the global length maximum; the printed string, beyond its length, is the returned factor value. A table entry is a computational result used in a statistical study, not an assertion that the repeated passage has one universal literary cause.

Structural Tensions¶

The exact optimization relation itself does not establish an opposed-pressure tradeoff. Symbolization, overlap policy, and tie handling must be stated, but the cited cases do not show that two defining objectives cannot be satisfied together. Engineering choices within a particular detector may have their own costs; those costs are not made universal by the name of this problem.

Structural–Framed Character¶

This entry is structural within a string-computation frame: its five roles can be recognized in code-derived and natural-language sequences, but exact contiguous sequence equality remains necessary.

Evaluative weight: A longer repeated factor is optimal by the declared length criterion; it is not automatically more useful, suspicious, or meaningful.
Human-practice dependence: People choose tokenization and use returned values, but their judgment does not replace the exact two-occurrence test.
Institutional origin: AdaCore's and Dębowski's projects demonstrate uses; neither institution makes a repeat qualify by decree.
Vocabulary travel: “Repeat” can describe events outside strings, but the named problem does not travel there without an ordered symbol sequence and contiguous equality.
Import versus recognition: An analyst recognizes the five roles in a new sequence. Importing AdaCore's hashing into a literary text, or a literary interpretation into code hashes, would add an application-specific claim.

Its character: a formally specified optimization relation whose input representations can vary inside string and sequence analysis, with the exact factor roles limiting its wider reach.

Structural Core vs. Domain Accent¶

The skeletal relation is one sequence → two equal contiguous occurrences → global length maximum → returned factor. Its domain accent is constitutive: the candidates are symbol runs in one ordered sequence under exact equality. The code and literary settings vary the symbols and purpose, not those requirements. Replacing them with generic repeated events or an approximate similarity score would erase the named identity.

The live Optimization Prime supplies a portable parent relation: candidate choices, feasibility constraints, an objective, and exact global optimality. In this child, those roles are factor values, two-start exact-repeat eligibility, factor length, and one returned maximum. Other optimization problems need no strings, so the parent survives removal of the child's domain accent. Whether a broader substrate-independent “longest repeat” concept merits a separate Prime is a future-prime question. This named entry does not clear the Prime bar by renaming exact contiguous factors as repetition in general.

This entry is a kind of Optimization.

Optimization is the typed Prime parent by strict subsumption: the problem chooses among repeat-qualified factor values and maximizes length globally. It retains a string-specific differentia absent from optimization in general. The Substring entry concerns a factor value whether it occurs once or many times; this entry is a problem over such values, not a subtype of one value. Suffix Tree is a solving representation, not a necessary genus. Pattern Matching begins with a supplied query pattern, whereas here the maximal self-repeat is unknown before solving.

Relationships to Other Abstractions¶

Current abstraction Longest Repeated Substring Problem Domain-specific

Parents (1) — outgoing typed relations

Longest Repeated Substring Problem is a kind of Optimization Prime

The longest repeated substring problem is exact discrete optimization over repeat-qualified factor values.

Hierarchy path (1) — routes to 1 parentless root

Longest Repeated Substring Problem → is a kind of Optimization

Neighborhood in Abstraction Space¶

Longest Repeated Substring Problem sits in a moderately populated region (47^th percentile for distinctiveness): it has near-neighbors but no dense thicket of look-alikes.

Family — Abstract Algebra & Category Theory (25 abstractions)

Nearest neighbors

Computed from structural-signature embeddings · 2026-10-25

Not to Be Confused With¶

Substring: a contiguous factor can exist once; this problem requires at least two distinct starts and maximizes length.
Suffix tree: a data structure can solve the problem, but the same input/output specification survives a different implementation.
Pattern matching: the supplied pattern is known in advance; the longest repeated factor is discovered.
Longest common substring: a common factor across two declared inputs changes the one-input identity.
Length-only statistic: it reports the optimum length without the actual factor value.
Nonoverlapping or at-least-k variants: each changes the qualifying occurrence rule. A nonoverlap answer needs a correct distance check across occurrence starts; the frozen seed's adjacent-suffix shortcut is not adopted here.

References¶

[1] Łukasz Dębowski (2015). “Maximal Repetitions in Written Texts: Finite Energy Hypothesis vs. Strong Hilberg Conjecture.” Entropy 17(8): 5903–5919. DOI 10.3390/e17085903. Publisher record; inspected full published text. Relevant: §2 equation (3), §3 methods and Tables 1–3. Direct publisher access was rate-limited during review; the full text was inspected on the ResearchGate-hosted copy. registry ↩a ↩b ↩c ↩d ↩e ↩f ↩g ↩h ↩i ↩j

[2] Stanford University, CS166 (Spring 2014), “Suffix Trees,” lecture slides (course archive); “Longest Repeated Substring” section. Full university PDF. Relevant: PDF pages 34–39 on the problem, two suffixes, deepest internal node, factor recovery, and the at-least-k extension. registry ↩a ↩b ↩c ↩d ↩e ↩f

[3] AdaCore (2017). “A Usable Copy-Paste Detector in A Few Lines of Python.” Full first-party implementation article. Relevant: “First Attempt” steps 1–3, “Results on GPS,” and the subsequent all-copy-pastes extension. registry ↩a ↩b ↩c ↩d ↩e ↩f ↩g