Name
Abstract | ||
|---|---|---|
Two strings X and Y are considered Abelian equal if the letters of X can be permuted to obtain Y (and vice versa). Recently, Alatabbi et al. (2015) considered the longest common Abelian factor problem in which we are asked to find the length of the longest Abelian-equal factor present in a given pair of strings. They provided an algorithm that uses O(sigma n(2)) time and O(sigma n) space, where n is the length of the pair of strings and sigma is the alphabet size. In this paper we describe an algorithm that uses O(n(2) log(2) n log* n) time and O(n log(2) n) space, significantly improving Alatabbi et al.'s result unless the alphabet is small. Our algorithm makes use of techniques for maintaining a dynamic set of strings under split, join, and equality testing (Melhorn et al., Algorithmica 17(2), 1997). |
Year | DOI | Venue |
|---|---|---|
2016 | 10.1007/978-3-319-46049-9_24 | Lecture Notes in Computer Science |
Field | DocType | Volume |
Abelian group,Combinatorics,Computer science,Sigma,Suffix tree,Alphabet | Conference | 9954 |
ISSN | Citations | PageRank |
0302-9743 | 3 | 0.47 |
References | Authors | |
5 | 6 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Golnaz Badkobeh | 1 | 95 | 14.12 |
| Travis Gagie | 2 | 643 | 63.61 |
| Szymon Grabowski | 3 | 385 | 36.12 |
| Yuto Nakashima | 4 | 57 | 19.52 |
| Simon J. Puglisi | 5 | 1132 | 75.14 |
| Shiho Sugimoto | 6 | 12 | 2.62 |