Abstract | ||
---|---|---|
Regularities in indeterminate strings have recently been a matter of interest because of their use in the fields of molecular biology, musical text analysis, cryptanalysis and so on. In this paper, we study the problem of reconstructing an indeterminate string from a border array. We present two efficient algorithms to reconstruct an indeterminate string from a valid border array - one using an unbounded alphabet and the other using minimum sized alphabet. We also propose an O(n^2) algorithm for reconstructing an indeterminate string from suffix array and LCP array. |
Year | DOI | Venue |
---|---|---|
2012 | 10.1016/j.jda.2011.08.002 | J. Discrete Algorithms |
Keywords | Field | DocType |
lcp array,valid border array,indeterminate string,indeterminate string inference algorithm,suffix array,border array,musical text analysis,molecular biology,efficient algorithm,unbounded alphabet | String searching algorithm,LCP array,Discrete mathematics,Combinatorics,Inference,Algorithm,Cryptanalysis,Suffix array,Indeterminate,Compressed suffix array,Mathematics,Alphabet | Journal |
Volume | ISSN | Citations |
10, | 1570-8667 | 4 |
PageRank | References | Authors |
0.47 | 17 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Sumaiya Nazeen | 1 | 8 | 1.57 |
M. Sohel Rahman | 2 | 488 | 56.99 |
Rezwana Reaz | 3 | 11 | 3.32 |