Publica
Hier finden Sie wissenschaftliche Publikationen aus den FraunhoferInstituten. String matching with involutions
 DurandLose, 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: 9783642328947 ISBN: 9783642328930 (print) ISBN: 3642328938 pp.106117 
 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 nonoverlapping factors we obtain an algorithm running O(TP) 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.