# Consultar departamento

Por fecha Por autores Por títulos Por temas (CDU)

Del documento Todo RECERCAT

# Mi RECERCAT

Entrar Alertas por correo-e

Utilizad este identificador para citar o enlazar este documento: http://hdl.handle.net/2072/212292

 Título: Algorithmic aspects of bio-inspired string operations Klaus-Peter, Leupold Agència de Gestió d'Ajuts Universitaris i de Recerca; Universitat Rovira i Virgili. Departament de Filologies Romàniques We present building blocks for algorithms for the efficient reduction of square factor, i.e. direct repetitions in strings. So the basic problem is this: given a string, compute all strings that can be obtained by reducing factors of the form zz to z. Two types of algorithms are treated: an offline algorithm is one that can compute a data structure on the given string in advance before the actual search for the square begins; in contrast, online algorithms receive all input only at the time when a request is made. For offline algorithms we treat the following problem: Let u and w be two strings such that w is obtained from u by reducing a square factor zz to only z. If we further are given the suffix table of u, how can we derive the suffix table for w without computing it from scratch? As the suffix table plays a key role in online algorithms for the detection of squares in a string, this derivation can make the iterated reduction of squares more efficient. On the other hand, we also show how a suffix array, used for the offline detection of squares, can be adapted to the new string resulting from the deletion of a square. Because the deletion is a very local change, this adaption is more eficient than the computation of the new suffix array from scratch. 17-06-2013 AlgorithmStringBioinformaticsDuplicationSuffix array L'accés als continguts d'aquest document queda condicionat a l'acceptació de les condicions d'ús establertes per la següent llicència Creative Commons: http://creativecommons.org/licenses/by-nc-nd/3.0/es/ 10 p. Informe Els ajuts de l'AGAUR;2009 BP-B00052

## Documentos con el texto completo de este documento

Ficheros Tamaño Formato
2009 BP-B 00052.pdf 244.9 KB PDF

Coordinación

Patrocinio