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 - Funding Information:
This work was funded by ImPACT Program of Council for Science, Technology and Innovation (Cabinet Office, Government of Japan), Tohoku University Division for Interdisciplinary Advance Research and Education, and JSPS KAKENHI Grant Numbers JP15H05706, JP24106010, JP26280003.
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 - http://www.scopus.com/inward/record.url?scp=85010704938&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85010704938&partnerID=8YFLogxK
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 -