Longest Gapped Repeats and Palindromes

Dumitran, Marius; Gawrychowski, Paweł; Manea, Florin

doi:10.23638/dmtcs-19-4-4

Cited by 11Algorithms and Data Compressionsemigroups and automata theoryGenome Rearrangement Algorithms

The DOI matches its Crossref record; 55 of the 55 references it cites were found in a registry or an index; none of the 29 sources its claims cite is checked for support yet.

Longest Gapped Repeats and Palindromes

Open access

Dumitran, Marius, Gawrychowski, Paweł, Manea, Florin·2017·Discrete Mathematics & Theoretical Computer Science

DOI 10.23638/dmtcs-19-4-4

Open this paper in CoChat — free account Open PDF

Abstract

A gapped repeat (respectively, palindrome) occurring in a word $w$ is a factor $uvu$ (respectively, $u^Rvu$) of $w$. In such a repeat (palindrome) $u$ is called the arm of the repeat (respectively, palindrome), while $v$ is called the gap. We show how to compute efficiently, for every position $i$ of the word $w$, the longest gapped repeat and palindrome occurring at that position, provided that the length of the gap is subject to various types of restrictions. That is, that for each position $i$ we compute the longest prefix $u$ of $w[i..n]$ such that $uv$ (respectively, $u^Rv$) is a suffix of $w[1..i-1]$ (defining thus a gapped repeat $uvu$ -- respectively, palindrome $u^Rvu$), and the length of $v$ is subject to the aforementioned restrictions. Comment: This is an extension of the conference papers "Longest $\alpha$-Gapped Repeat and Palindrome", presented by the second and third authors at FCT 2015, and "Longest Gapped Repeats and Palindromes", presented by the first and third authors at MFCS 2015

CoChat Summary

TL;DR

The paper gives algorithms to construct longest previous gapped repeat/palindrome tables for each position of a word under several gap restrictions. It obtains linear or near-linear bounds for bounded-gap and position-dependent lower bounds, and $O(\alpha n)$ bounds for $\alpha$-gapped repeats and palindromes.

Key findings

For gap length between $g$ and $G$, the longest previous reverse-factor array $LPrF_{g,G}[\cdot]$ can be built in $O(n)$ time, while the longest previous factor array $LPF_{g,G}[\cdot]$ can be built in $O(n\log n)$ time; consequently the longest gapped palindrome is found in linear time and the longest gapped repeat in $O(n\log n)$ time.
For a position-dependent lower bound $g(i)$, both $LPrF_g[\cdot]$ and $LPF_g[\cdot]$ can be constructed in linear time, and the longest gapped palindrome or repeat satisfying $|v|\ge g(i)$ is found in linear time.
For $\alpha$-gapped repeats $uvu$ and palindromes $u^Rvu$ with $|uv|\le \alpha |u|$, the arrays $LRep_\alpha[\cdot]$ and $LPal_\alpha[\cdot]$ can be constructed in $O(\alpha n)$ time; the longest such repeat or palindrome can also be found in $O(\alpha n)$ time.
The paper notes that the number of maximal $\alpha$-gapped repeats or palindromes is $\Theta(\alpha n)$, and it uses algorithms from prior work that find all such maximal structures in optimal $\Theta(\alpha n)$ time.

Methods

The algorithms are string-data-structure based, using suffix arrays, LCP queries, dictionaries of basic factors, runs, interval union-find structures, and weighted level ancestor queries; for palindromes, suffix arrays are built for $w0w^R$.
For Problem 1(a), a sliding window over ranges of length $\delta=G-g$ and interval union-find give linear time; Problem 1(b) splits by arm length $2^k$, uses basic-factor occurrence representations, and runs in $O(n\log n)$.
Problem 2 is reduced to maintaining ordered lists via $L^+[i]$ chains and solving offline union-find/weighted-level-ancestor queries in linear time; Problem 3 uses block encodings, lemmas for compact occurrence reporting, and the set of all maximal $\alpha$-gapped repeats/palindromes to compute the arrays in $O(\alpha n)$.

Limitations

Stated in the paper: it remains open whether Problem 1(b) can be solved faster, whether the longest gapped repeats with gap between $g$ and $G$ can be found in linear time, whether the longest $\alpha$-gapped repeat or palindrome can be found faster than $O(\alpha n)$, and whether the Problem 3 arrays can be constructed without first producing all maximal $\alpha$-gapped repeats and palindromes.
Evident from the text: no implementation or empirical evaluation is reported; the results are asymptotic and rely on the unit-cost RAM with logarithmic word size and integer-alphabet assumptions.
Evident from the text: the bounded-gap repeat table $LPF_{g,G}[\cdot]$ has $O(n\log n)$ complexity, so it is not linear like the corresponding palindrome table.

Model-written summary. Check it against the paper before relying on it.

Integrity signals

Registry

Crossref · 10.23638/dmtcs-19-4-4

Cites

55 of 55 references verified0 citation errors · 0 not checkable

Statistics

Nothing to recompute.

Fig. 2 Proof of Theorem 1: Construction of the ranges J 1 , J 2 , J 3 for some range I k , and of the sliding window J ′ i ∪ J ′′ i for some i ∈ I kFrom the PDF

Fig. 3 Proof of Theorem 2: Occurrences of w [ i..i + 2 k -1] inside w [ i -G -2 k +1 ..i -g -1] : one separate occurrence, and a run containing three occurrences. The separate occurrence can be prolonged to produce a gapped palindrome uvu , which is not, however, long enough as it does not reach the range between i -G and i -g . The rightmost occurrence in the run produces the gapped repeat w [ i..i + 2 k -1] v ′ w [ i..i + 2 k -1] , which fulfils the conditions imposed on the gap.From the PDF

Fig. 5 Proof of Theorem 7: Segment of w , split into blocks of length log n . In this segment, z is a k -block of length 2 k log n . For each factor y , of length 2 k -1 log n , occurring in the first log n symbols of z (not necessarily a sequence of blocks), we find the occurrences of y that correspond to sequences of 2 k -1 blocks, and start at most (8 α +2) | y | = (4 α +1) · 2 k log n symbols (or, alternatively, (4 α +1) · 2 k blocks) to the left of the considered z . These y factors may appear as runs or as separate occurrences. Some of them can be extended to form an α -gapped repeat u 1 vu 2 = uvu such that the respective occurrence of y has the same offset in u 1 as the initial y in u 2 .From the PDF

Fig. 6 Proof of Theorem 8: Segment of w , split into blocks of length log n . In this segment, z is a k -block of length 2 k log n . For each factor y , of length 2 k -1 log n , occurring in the first log n symbols of z (not necessarily a sequence of blocks), we find the occurrences of y R that correspond to sequences of 2 k -1 blocks, and start at most (8 α +2) | y | = (4 α +1) · 2 k log n symbols (or, alternatively, (4 α +1) · 2 k blocks) to the left of the considered z . These y R factors may appear as runs or as separate occurrences. Some of them can be extended to form an α -gapped palindrome u R vu such that the respective occurrence of y R is the mirror image of the initial y in u 2 .From the PDF

Fig. 7 Proof of Theorem 9: p = uvu is a maximal α -gapped palindrome (here α = 2 ) with | v | = δ and | u | = ℓ . We define r = ⌊ ( α -1) ℓ -δ α +1 ⌋ = ⌊ ℓ -δ 3 ⌋ . This allows us to define the interval I p , where the right arm of an α -gapped palindrome obtained from p may start. Further, y R v ′′ y is an example of such an α -gapped palindrome; t R v ′ t is a gapped palindrome obtained from p , which is not α -gapped: it's right arm does not start in I p . The interval I p has weight j + ℓ -1 .From the PDF

Claims the paper makes

0 Valid · 5 Not valid · 27 Not checked · 89 Own results and interpretations

A result the paper states — it cites no source for it, so there is none to check. The quote shows it is in the paper.
In the paper
“Similarly to the previous cases, we check in O ( α ) time which is the longest α -gapped repeat obtained by pairing one of these occurrences to y , and extending them similarly to the left and right.”
plain
- Rests on an assumption not shown here.
A result the paper states — it cites no source for it, so there is none to check. The quote shows it is in the paper.
In the paper
“Theorem 2 Problem 1(b) can be solved in O ( n log n ) time.”
plain
n = 2
A result the paper states — it cites no source for it, so there is none to check. The quote shows it is in the paper.
In the paper
“The algorithm computes H [ · ] correctly. Indeed, we set H [ ℓ ] = g when we process an interval I j of weight g that contains ℓ , and no other interval of greater weight contained ℓ .”
plain
states a cause
A result the paper states — it cites no source for it, so there is none to check. The quote shows it is in the paper.
In the paper
“This shows that the total number of find operations is O ( k + | ∪ j =1 ,k I j | ) = O ( n + k ) .”
boosted
states an association
A result the paper states — it cites no source for it, so there is none to check. The quote shows it is in the paper.
In the paper
“The right arm u 2 of such a repeat is contained in a factor w [ m log n +1 .. ( m +17)log n ] of w , while u 1 surely occurs in a factor x = w [ m log n -16 α log n +1 .. ( m +17)log n ] (or, if m log n -16 α log n + 1 ≤ 0 , then in a factor x = w [1 .. ( m + 17) log n ] ); in total, there are O ( n/ log n ) such x factors.”
plain
- Rests on an assumption not shown here.

85 more claims

Create a free account to see all 121 claims and to verify the 13 references still open.

See all claims — free account

It may state two separate claims as one. 13
The quote only partly states this claim. 3
Probably not a substantial claim. 18

Create a free account to see these claims.

Create a free account to see these assumptions.

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

Each contradiction between two passages listed here was confirmed by an independent check.

Rated minor: it would not touch a result — a value no result rests on, a p-value that stays on the same side of the significance level, or a conflict that is clerical, resolved elsewhere in the paper, or outside its own findings.
In the paper
- § 1 Introduction · p. 2
  “with g ≤ | v | < G”
- § 1 Introduction · p. 2
  “with g < | v | ≤ G”
Rated minor: it would not touch a result — a value no result rests on, a p-value that stays on the same side of the significance level, or a conflict that is clerical, resolved elsewhere in the paper, or outside its own findings.
In the paper
- § 4 Lower bounded gap · p. 18
  “Lemma 6 Given a word w , let L [ i ] = min { j | j < i, LCP ( j, i ) ≥ LCP ( k, i ) for all k < i } .”
- § 4 Lower bounded gap · p. 18
  “L [ i ] = B > [ i ] if LCP ( B > [ i ] , i ) > LCP ( B < [ i ] , i ) or LCP ( B > [ i ] , i ) = LCP ( B < [ i ] , i ) and B > [ i ] > B < [ i ]”
Rated minor: it would not touch a result — a value no result rests on, a p-value that stays on the same side of the significance level, or a conflict that is clerical, resolved elsewhere in the paper, or outside its own findings.
In the paper
- § 3 Lower and upper bounded gap · p. 13
  “Clearly, knowing B [ i ] means knowing LPrF g,G [ i ] .”
- § 3 Lower and upper bounded gap · p. 13
  “Theorem 2 Problem 1(b) can be solved in O ( n log n ) time.”

3 of 3

Introduction to algorithms
Grossman, P. (2009) · Discrete Mathematics for Computing · doi:10.1007/978-0-230-37405-8_1 · Cited by 8,834
Fast Pattern Matching in Strings
Knuth, D. E., Morris, Jr., & Pratt, V. R. (1977) · SIAM Journal on Computing · doi:10.1137/0206024 · Cited by 2,936
The Art of Computer Programming. Volume 1: Fundamental Algorithms.
Odeh, R. E., & Knuth, D. E. (1969) · Journal of the American Statistical Association · doi:10.2307/2283757 · Cited by 2,525
The Art of Computer Programming
Worlton, W. J. (1968) · Nuclear Science and Engineering · doi:10.13182/nse68-a19548 · Cited by 2,251
Combinatorics on words
Lothaire, M. (1984) · HAL · Cited by 1,753
Introduction to Analytic Number Theory
Apostol, T. M. (1976) · Undergraduate texts in mathematics · doi:10.1007/978-1-4757-5579-4 · Cited by 1,583
The LCA Problem Revisited
Bender, M. A., & Farach-Colton, M. (2000) · Lecture notes in computer science · doi:10.1007/10719839_9 · Cited by 815
Algorithms on Strings
Crochemore, M., Hancart, C., & Lecroq, T. (2007) · Cambridge University Press eBooks · doi:10.1017/cbo9780511546853 · Cited by 676
Finding patterns common to a set of strings
Angluin, D. (1980) · Journal of Computer and System Sciences · doi:10.1016/0022-0000(80)90041-0 · Cited by 616
Telomeres and telomerase
Chan, S. R. W. L., & Blackburn, E. H. (2004) · Philosophical Transactions of the Royal Society of London. Series B: Biological Sciences · doi:10.1098/rstb.2003.1370 · Cited by 595

Show all 55 references

Research works printed but not linked: 8

H. Bannai, T. I, S. Inenaga, Y. Nakashima, M. Takeda, and K. Tsuruta. The Runs Theorem. CoRR , abs/1406.0263, 2014. · arXiv
M. Crochemore and W. Rytter. Sqares, cubes, and time-space efficient string searching. Algorithmica , 13 (5):405-425, 1995.
M. Crochemore, R. Kolpakov, and G. Kucherov. Optimal bounds for computing α -gapped repeats. In Proc. LATA 2016 , volume 9618 of LNCS , pages 245-255, 2016.
M. Dumitran and F. Manea. Longest gapped repeats and palindromes. In Proc. MFCS 2015 , volume 9234 of LNCS , pages 205-217. Springer, 2015.
A. Ehrenfeucht and G. Rozenberg. Finding a Homomorphism Between Two Words is NP-Complete. Inf. Process. Lett. , 9(2):86-88, 1979.
N. J. Fine and H. S. Wilf. Uniqueness theorem for periodic functions. Proceedings of the American Mathematical Society , 16:109-114, 1965.
P. Gawrychowski and F. Manea. Longest α -gapped repeat and palindrome. In Proc. FCT 2015 , volume 9210 of LNCS , pages 27-40. Springer, 2015.
J. Justin. On a paper by Castelli, Mignosi, Restivo. ITA , 34(5):373-377, 2000.

Optimal Bounds for Computing $$\alpha $$ α -gapped Repeats
Crochemore, M., Kolpakov, R. M., & Kucherov, G. (2016) · Lecture notes in computer science · doi:10.1007/978-3-319-30000-9_19 · Cited by 17
Efficient representation and counting of antipower factors in words
Kociumaka, T., Radoszewski, J., Rytter, W., Straszyński, J., Waleń, T., & Zuba, W. (2021) · Information and Computation · doi:10.1016/j.ic.2021.104779 · Cited by 9
Optimal searching of gapped repeats in a wordPreprint
Crochemore, M., Kolpakov, R. M., & Kucherov, G. (2015) · arXiv (Cornell University) · doi:10.48550/arxiv.1509.01221 · Cited by 6
On the number of gapped repeats with arbitrary gap
Kolpakov, R. M. (2018) · Theoretical Computer Science · doi:10.1016/j.tcs.2018.03.007 · Cited by 5
Reversed Lempel–Ziv Factorization with Suffix Trees
Köppl, D. (2021) · Algorithms · doi:10.3390/a14060161 · Cited by 2

See all 11

Authors: Dumitran, M., Gawrychowski, P., & Manea, F.
Affiliations: University of Wrocław (PL)
ORCID: Gawrychowski, Paweł
Venue: Discrete Mathematics & Theoretical Computer Science
Publisher: Centre pour la Communication Scientifique Directe (CCSD)
Published: 2017-10-13
Volume: Vol. 19 no. 4, FCT '15
Issue: special issue FCT'15
ISSN: 1365-8050 (ISSN-L)
DOI: 10.23638/dmtcs-19-4-4
OpenAlex: W2950226630
Cited by: 11
References: 55
Citations by year: 2025: 1 · 2021: 4 · 2019: 1 · 2018: 2
FWCI: 0.84
Type: journal article
Language: en
Open access: diamond
doi.org
Licence: cc-by
creativecommons.org/licenses/by/4.0 (am)
creativecommons.org/licenses/by/4.0 (vor)
creativecommons.org/licenses/by/4.0 (tdm)
Locations: Discrete Mathematics & Theoretical Computer Science (publishedVersion, cc-by)
arXiv (Cornell University) (submittedVersion, cc-by)
DOAJ (DOAJ: Directory of Open Access Journals) (submittedVersion, cc-by-sa)
arXiv (Cornell University) (cc-by)
Entrepôt pour orphelin (cc-by-nd)
Discrete Mathematics & Theoretical Computer Science (cc-by)
Funders: Deutsche Forschungsgemeinschaft (596676)
Topics: Physical Sciences › Mathematics › Theoretical Computer Science › Algorithms and Data Compression
Physical Sciences › Computer Science › Computational Theory and Mathematics › semigroups and automata theory
Life Sciences › Biochemistry, Genetics and Molecular Biology › Genetics › Genome Rearrangement Algorithms
Keywords: palindromes, string algorithms

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

A language model drew the claims from the paper on 2026-11-14, under version 3 of the claim definition (model deepseek-v4.1-flash, prompt extract-v3).

A second model labelled each claim on 2026-11-14 (model jev-1.13-20260917, definition revision gold-guideline-v0.2).

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review

How to cite

Cite CoChat for the checks on this page, and the paper for its own findings.

This page: CoChat. (2026). Citation check: Longest Gapped Repeats and Palindromes. https://app.cochat.ai/papers/10.23638/dmtcs-19-4-4
The paper: Dumitran, M., Gawrychowski, P., & Manea, F. (2017). Longest Gapped Repeats and Palindromes. Discrete Mathematics & Theoretical Computer Science. https://doi.org/10.23638/dmtcs-19-4-4

Data sources

Bibliographic data: Semantic Scholar, OpenAlex, Crossref.

Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).

Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.

Longest Gapped Repeats and Palindromes

Abstract

Overview

CoChat Summary

TL;DR

Key findings

Methods

Limitations

Integrity signals

Figures

Verification

Claims the paper makes

Self-check

Citations

Cites

Cited by

Related

Metadata

Record

About these checks

How to cite

Data sources