Universal reconstruction of a string
| Autor: | Tomasz Kociumaka, Tomasz Waleń, Jakub Radoszewski, Wojciech Rytter, Paweł Gawrychowski |
|---|---|
| Rok vydání: | 2020 |
| Předmět: |
General Computer Science
Computer science String (computer science) Suffix array Palindrome 0102 computer and information sciences 02 engineering and technology 01 natural sciences Substring Theoretical Computer Science law.invention Combinatorics 010201 computation theory & mathematics law 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing |
| Zdroj: | Theoretical Computer Science. 812:174-186 |
| ISSN: | 0304-3975 |
| Popis: | 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 Karkkainen et al. (2006) [23] . This is a full version of a paper presented at WADS 2015 [18] . |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect