Back to Search
Start Over
Efficient computation of longest single-arm-gapped palindromes in a string.
- Source :
-
Theoretical Computer Science . Apr2020, Vol. 812, p160-173. 14p. - Publication Year :
- 2020
-
Abstract
- • A new variant of approximate palindromes called single-arm-gapped palindromes. • Efficient algorithms to compute maximal single-arm-gapped palindromes in a string. • Experimental results to compare the proposed methods in practice. In this paper, we introduce new types of approximate palindromes called single-arm-gapped palindromes (shortly SAGPs). A SAGP contains a gap in either its left or right arm, which is in the form of either w g u c u R w R or w u c u R g w R , where w and u are non-empty strings, w R and u R are respectively the reversed strings of w and u , g is a string called a gap, and c is either a single character or the empty string. Here we call wu and u R w R the arm of the SAGP, and | u v | the length of the arm. We classify SAGPs into two groups: those which have u c u R as a maximal palindrome (type-1), and the others (type-2). We propose several algorithms to compute type-1 SAGPs with longest arms occurring in a given string, based on suffix arrays. Then, we propose a linear-time algorithm to compute all type-1 SAGPs with longest arms, based on suffix trees. Also, we show how to compute type-2 SAGPs with longest arms in linear time. We also perform some preliminary experiments to show practical performances of the proposed methods. [ABSTRACT FROM AUTHOR]
- Subjects :
- *PALINDROMES
*ARM
*ALGORITHMS
Subjects
Details
- Language :
- English
- ISSN :
- 03043975
- Volume :
- 812
- Database :
- Academic Search Index
- Journal :
- Theoretical Computer Science
- Publication Type :
- Academic Journal
- Accession number :
- 141828932
- Full Text :
- https://doi.org/10.1016/j.tcs.2019.10.025