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
International Conference on Unconventional Computation and Natural Computation (UCNC) <11, 2012, Orleans>
Conference Paper
Fraunhofer FIRST ()

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.