dc.contributor |
Agència de Gestió d'Ajuts Universitaris i de Recerca |
dc.contributor |
Universitat Rovira i Virgili. Departament de Filologies Romàniques |
dc.contributor.author |
Klaus-Peter, Leupold |
dc.date.accessioned |
2013-06-17T15:57:52Z |
dc.date.available |
2013-06-17T15:57:52Z |
dc.date.created |
2012-11-19 |
dc.date.issued |
2013-06-17 |
dc.identifier.uri |
http://hdl.handle.net/2072/212292 |
dc.format.extent |
10 p. |
dc.language.iso |
cat |
dc.relation.ispartofseries |
Els ajuts de l'AGAUR;2009 BP-B00052 |
dc.rights |
info:eu-repo/semantics/openAccess |
dc.rights |
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/ |
dc.source |
RECERCAT (Dipòsit de la Recerca de Catalunya) |
dc.subject.other |
Algorithm |
dc.subject.other |
String |
dc.subject.other |
Bioinformatics |
dc.subject.other |
Duplication |
dc.subject.other |
Suffix array |
dc.title |
Algorithmic aspects of bio-inspired string operations |
dc.type |
info:eu-repo/semantics/report |
dc.embargo.terms |
cap |
dc.description.abstract |
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. |