TY - JOUR

T1 - Efficient computation of longest single-arm-gapped palindromes in a string

AU - Narisada, Shintaro

AU - Hendrian, Diptarama

AU - Narisawa, Kazuyuki

AU - Inenaga, Shunsuke

AU - Shinohara, Ayumi

N1 - Funding Information:
The research of Shintaro Narisada, Kazuyuki Narisawa, and Ayumi Shinohara was supported by JSPS KAKENHI Grant Numbers JP15H05706 , JP24106010 , and ImPACT Program “Tough Robotics Challenge” of Japan Science and Technology Agency . The research of Diptarama Hendrian is supported by Tohoku University Division for Interdisciplinary Advance Research and Education . The research of Shunsuke Inenaga was supported by JSPS KAKENHI Grant Numbers JP26280003 and JP17H01697 . The authors thank anonymous referees for their useful suggestions for improving the quality of the paper and for pointing out some errors in the previous version.
Publisher Copyright:
© 2019 Elsevier B.V.

PY - 2020/4/6

Y1 - 2020/4/6

N2 - 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 wgucuRwR or wucuRgwR, where w and u are non-empty strings, wR and uR 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 uRwR the arm of the SAGP, and |uv| the length of the arm. 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 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.

AB - 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 wgucuRwR or wucuRgwR, where w and u are non-empty strings, wR and uR 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 uRwR the arm of the SAGP, and |uv| the length of the arm. 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 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.

KW - Palindromes

KW - String algorithms

KW - Suffix arrays

KW - Suffix trees

UR - http://www.scopus.com/inward/record.url?scp=85074129888&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85074129888&partnerID=8YFLogxK

U2 - 10.1016/j.tcs.2019.10.025

DO - 10.1016/j.tcs.2019.10.025

M3 - Article

AN - SCOPUS:85074129888

SN - 0304-3975

VL - 812

SP - 160

EP - 173

JO - Theoretical Computer Science

JF - Theoretical Computer Science

ER -