Longest Repeated Substring Problem¶
Find a longest contiguous factor that occurs at two distinct starts in one sequence, and return that factor.
Core Idea¶
The longest repeated substring problem asks for one longest contiguous factor that occurs at two different starts in a single finite sequence. The symbols and equality rule must be declared. The two occurrences may overlap; ana occurs in banana at zero-based starts 1 and 3. Among all such repeated factors, return one whose length is globally maximal. A result can also include its length and positions, but a length alone does not identify the requested factor. Dębowski's formal definition permits overlapping occurrences[1]. Ties and inputs with no nonempty repeat need stated output conventions.
This is a problem specification rather than one algorithm. A suffix tree can organize suffixes so that a deepest qualifying internal node yields a longest shared factor[2]. The tree, an end marker, and a chosen traversal are solving devices; the repeated-factor conditions define the answer.
Scope of Application¶
AdaCore applies a longest-repeat search to one ordered sequence of hash codes derived from source-code features.[3] It maps a repeated run back to candidate duplicated code spans and source locations[3]. Equality is relative to that normalized representation, so a match does not prove byte-identical source.
Dębowski studies cleaned literary texts as character or word sequences, computes maximal repeated factors for whole texts, and prints actual factor values in Tables 1–3[1]. The lengths support a study of text repetition growth.[1] The published tables do not provide paired numeric start offsets.[1] These two settings share the same exact one-input optimization roles, although their representations and purposes differ.
Clarity¶
Distinguish a factor value, its occurrence positions, and its length. The value ana, starts 1 and 3, and length 3 answer different questions about banana. A report of only 3 gives the optimal length but not the factor. Requiring nonoverlapping positions, at least three occurrences, an approximate match, or a supplied query pattern changes the task. Stanford treats an at-least-k occurrence version separately[2].
The equality rule also matters. Equal code hashes can correspond to source fragments that are not byte-identical[3]. A cleaned text and a raw document may have different repeat values. State the symbol unit before interpreting the answer.
Manages Complexity¶
Many factor values and pairs of starts can be considered. The specification reduces them to an eligibility test—two exact contiguous occurrences in one sequence—and a length objective. Suffixes expose shared prefixes; a deepest shared path in a suitable suffix tree identifies an optimum[2]. This is one efficient solution route, not a requirement that every implementation use that structure or inherit an unconditional linear bound.
Abstract Reasoning¶
For a proposed result, ask whether its equal contiguous factor really occurs at two distinct starts and whether any longer qualifying factor exists. The first question establishes feasibility; the second establishes global optimality. If overlaps are forbidden, the feasible set changes. If the output contains only a number, the result is a length projection. These checks keep the problem apart from a data structure, a partial match, and a general search for any repeated passage.
Knowledge Transfer¶
The five roles—declared sequence, distinct starts, exact contiguous factor, global length maximum, and returned factor—can be recognized in AdaCore's code-hash setting[3]. They can also be recognized in Dębowski's literary-text setting[1]. The algorithms and interpretations need not transfer: a code-copy candidate and a quoted literary passage have different meanings. The live Optimization Prime supplies the portable choice/constraint/objective pattern; the exact symbol-sequence requirements keep this named problem domain-specific.
Example¶
In AdaCore's first copy-paste detector, code features form one hash sequence, a longest repeated run is found, and its source-code spans are returned for inspection[3]. Mapped back: the hash sequence fixes the input and equality rule; two offsets witness repetition; equal adjacent hashes form the contiguous factor; maximum run length supplies the optimum; the mapped span is the returned value. AdaCore's later all-copy-pastes extension is broader than this single-optimum example.[3]
Dębowski's whole-text tables provide a second, unlike case: each cleaned literary work is searched as one sequence and an actual maximal repeated passage is printed with its length[1]. Mapped back: the text and tokenization fix the input; the paper's definition requires two starts and exact contiguity; the table's maximal entry supplies the global optimum and returned value. Numeric paired offsets are not printed.[1] The statistical use of the length does not erase the value-output computation.
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 (47th percentile for distinctiveness): it has near-neighbors but no dense thicket of look-alikes.
Family — Abstract Algebra & Category Theory (25 abstractions)
Nearest neighbors
- Substring — 0.89
- Locally catenative sequence — 0.87
- List (computing) — 0.86
- Sierpiński Graph — 0.85
- Noncontracting Grammar — 0.85
Computed from structural-signature embeddings · 2026-10-25
Not to Be Confused With¶
- Substring: one contiguous factor value may occur only once; this problem requires two starts and a maximum.
- Suffix tree: a useful solving representation, not the problem itself.
- Pattern matching: a query pattern is supplied, while this factor is discovered.
- Longest common substring: its occurrences are sought across two supplied inputs rather than as a self-repeat of one.
- Length-only repeat statistic: the optimum length without one factor value.
- Nonoverlap or at-least-
kvariants: these change which factors qualify. The frozen seed's adjacent-suffix nonoverlap shortcut is not adopted as a general rule.
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
[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
[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