RoSA '02 (Rouen, June 6-7, 2002)


Computation of longest extension functions


Grégory KUCHEROV
Gregory.Kucherov@loria.fr
http://www.loria.fr/~kucherov
INRIA/LORIA, 615, rue du Jardin Botanique, BP 101, 54602 Villers-les-Nancy Cedex, FRANCE


We first present the Manacher algorithm (1975) - a beautiful algorithm for computing, in linear time, all palindromes in a string. We then turn to the problem of computing longest extension functions, that arises in particular in computing periodicities in strings. For that problem, we show an algorithm that presents an interesting analogy with the Manacher algorithm and slightly improves the original Main and Lorentz algorithm for this problem (1984).


Retour à la page d'accueil
Back to home page