Computing Longest Single-arm-gapped Palindromes in a String
Theory and Practice of Computer Science - 43rd International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2017),
Lecture Notes in Computer Science Vol.10139, pp.375-386
(2017), [peer-reviewed]
Event Date:
January 16-20, 2017
Abstract / 概要
We introduce new types of approximate palindromes called single-arm-gapped palindromes (SAGPs). A SAGP contains a gap in either its left or right arm, which is in the form of either $wgucu^Rw^R$ or $wucu^Rgw^R$, where $w$ and $u$ are non-empty strings, $w^R$ and $u^R$ are their reversed strings respectively, $g$ is a gap, and $c$ is either a single character or the empty string. We classify SAGPs into two groups: those which have $ucu^R$ as a maximal palindrome (type-1), and the others (type-2). We propose several algorithms to compute all type-1 SAGPs with longest arms occurring in a given string using suffix arrays, and them a linear-time algorithm based on suffix trees. We also show how to compute type-2 SAGPs with longest arms in linear time. We perform some preliminary experiments to evaluate practical performances of the proposed methods.