Marius Dumitran ; Paweł Gawrychowski ; Florin Manea - Longest Gapped Repeats and Palindromes

dmtcs:1337 - Discrete Mathematics & Theoretical Computer Science, October 13, 2017, Vol. 19 no. 4, FCT '15 - https://doi.org/10.23638/DMTCS-19-4-4
Longest Gapped Repeats and PalindromesArticle

Authors: Marius Dumitran ; Paweł Gawrychowski ; Florin Manea

    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


    Volume: Vol. 19 no. 4, FCT '15
    Section: special issue FCT'15
    Published on: October 13, 2017
    Accepted on: October 3, 2017
    Submitted on: October 12, 2016
    Keywords: Computer Science - Data Structures and Algorithms

    1 Document citing this article

    Consultation statistics

    This page has been seen 1133 times.
    This article's PDF has been downloaded 528 times.