Fraunhofer-Gesellschaft

Publica

Hier finden Sie wissenschaftliche Publikationen aus den Fraunhofer-Instituten.

String matching with involutions

 
: Grozea, C.; Manea, F.; Müller, M.; Nowotka, D.

:

Durand-Lose, J.; Jonoska, N.:
Unconventional computation and natural computation. 11th international conference, UCNC 2012 : Orléans, France, September 3 - 7, 2012; proceedings
Berlin: Springer, 2012 (Lecture Notes in Computer Science 7445)
ISBN: 978-3-642-32894-7
ISBN: 978-3-642-32893-0 (print)
ISBN: 3-642-32893-8
pp.106-117
International Conference on Unconventional Computation and Natural Computation (UCNC) <11, 2012, Orleans>
English
Conference Paper
Fraunhofer FIRST ()

Abstract
We propose a novel algorithm for locating in a text T every occurrence of a string that can be obtained from a given pattern P by successively applying antimorphic involutions on some of its factors. When the factors on which these involutions are applied overlap, a linear time algorithm is obtained. When we apply the involutions to non-overlapping factors we obtain an algorithm running O(|T||P|) in time and O(|P|) space, in the worst case. We also improve the latter algorithm to achieve linear average running time, when the alphabet of the pattern is large enough.

: http://publica.fraunhofer.de/documents/N-254385.html