Name
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(R)w(R) or wucuR gwR, 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. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1007/978-3-319-51963-0_29 | Lecture Notes in Computer Science |
DocType | Volume | ISSN |
Conference | 10139 | 0302-9743 |
Citations | PageRank | References |
1 | 0.41 | 11 |
Authors | ||
5 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Shintaro Narisada | 1 | 1 | 1.09 |
| Diptarama | 2 | 4 | 1.85 |
| Kazuyuki Narisawa | 3 | 33 | 6.82 |
| Shunsuke Inenaga | 4 | 595 | 79.02 |
| Ayumi Shinohara | 5 | 936 | 88.28 |