Name
Abstract | ||
|---|---|---|
A string s is said to be a gapped palindrome iff s = xyx(R) for some strings x, y such that |x| >= 1, |y| >= 2, and x(R) denotes the reverse image of x. In this paper we consider two kinds of gapped palindromes, and present efficient online algorithms to compute these gapped palindromes occurring in a string. First, we show an online algorithm to find all maximal g-gapped palindromes with fixed gap length g >= 2 in a string of length n in O(n log sigma) time and O(n) space, where s is the alphabet size. Second, we show an online algorithm to find all maximal lengthconstrained gapped palindromes with arm length at least A >= 1 and gap length in range [gmin, gmax] in O(n(g(max)-g(min)/A + log sigma)) time and O(n) space. We also show that if A is a constant, then there exists a string of length n which contains ohm(n(g(max) - g(min))) maximal LCGPs, which implies we cannot hope for a significant speed-up in the worst case. |
Year | DOI | Venue |
|---|---|---|
2016 | 10.1007/978-3-319-44543-4_15 | Combinatorial Algorithms |
Field | DocType | Volume |
Combinatorics,Palindrome,Sigma,Suffix tree,Physics,Alphabet | Conference | 9843 |
ISSN | Citations | PageRank |
0302-9743 | 0 | 0.34 |
References | Authors | |
0 | 5 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Yuta Fujishige | 1 | 5 | 2.47 |
| Michitaro Nakamura | 2 | 0 | 0.34 |
| Shunsuke Inenaga | 3 | 595 | 79.02 |
| Hideo Bannai | 4 | 620 | 79.87 |
| Masayuki Takeda | 5 | 902 | 79.24 |