TY - GEN
T1 - Computing longest single-arm-gapped palindromes in a string
AU - Narisada, Shintaro
AU - Diptarama,
AU - Narisawa, Kazuyuki
AU - Inenaga, Shunsuke
AU - Shinohara, Ayumi
N1 - Publisher Copyright:
© Springer International Publishing AG 2017.
PY - 2017
Y1 - 2017
N2 - 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 wgucuRwR or wucuRgwR, where w and u are non-empty strings, wR and uR 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 ucuR 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.
AB - 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 wgucuRwR or wucuRgwR, where w and u are non-empty strings, wR and uR 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 ucuR 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.
UR - https://www.scopus.com/pages/publications/85010704938
UR - https://www.scopus.com/pages/publications/85010704938#tab=citedBy
U2 - 10.1007/978-3-319-51963-0_29
DO - 10.1007/978-3-319-51963-0_29
M3 - Conference contribution
AN - SCOPUS:85010704938
SN - 9783319519623
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 375
EP - 386
BT - SOFSEM 2017
A2 - Baier, Christel
A2 - van den Brand, Mark
A2 - Eder, Johann
A2 - Hinchey, Mike
A2 - Margaria, Tiziana
A2 - Steffen, Bernhard
PB - Springer Verlag
T2 - 43rd Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2017
Y2 - 16 January 2017 through 20 January 2017
ER -