Journal Article
No Thumbnail Available
License
Closed AccessUniversal reconstruction of a string
| cris.lastimport.scopus | 2024-02-12T20:52:48Z |
| dc.abstract.en | Many properties of a string can be viewed as sets of dependencies between substrings of the string expressed in terms of substring equality. We design a linear-time algorithm which finds a solution to an arbitrary system of such constraints: a generic string satisfying a system of substring equations. This provides a general tool for reconstructing a string from different kinds of repetitions or symmetries present in the string, in particular, from runs or from maximal palindromes. The recursive structure of our algorithm in some aspects resembles the suffix array construction by Kärkkäinen et al. (2006) [23]. |
| dc.affiliation | Uniwersytet Warszawski |
| dc.contributor.author | Radoszewski, Jakub |
| dc.contributor.author | Rytter, Wojciech |
| dc.contributor.author | Waleń, Tomasz |
| dc.contributor.author | Kociumaka, Tomasz |
| dc.contributor.author | Gawrychowski, Paweł |
| dc.date.accessioned | 2024-01-26T11:19:38Z |
| dc.date.available | 2024-01-26T11:19:38Z |
| dc.date.issued | 2020 |
| dc.description.finance | Publikacja bezkosztowa |
| dc.description.volume | 812 |
| dc.identifier.doi | 10.1016/J.TCS.2019.10.027 |
| dc.identifier.issn | 0304-3975 |
| dc.identifier.uri | https://repozytorium.uw.edu.pl//handle/item/124223 |
| dc.identifier.weblink | https://doi.org/10.1016/j.tcs.2019.10.027 |
| dc.language | eng |
| dc.pbn.affiliation | computer and information sciences |
| dc.relation.ispartof | Theoretical Computer Science |
| dc.relation.pages | 174-186 |
| dc.rights | ClosedAccess |
| dc.sciencecloud | nosend |
| dc.subject.en | String recovery |
| dc.subject.en | Minimal spanning tree |
| dc.subject.en | Run in a string |
| dc.subject.en | Maximal palindromes |
| dc.title | Universal reconstruction of a string |
| dc.type | JournalArticle |
| dspace.entity.type | Publication |