Abstract

The talk deals with the computation of repetitions occurring in a string. It first shows an optimal O(n log n)-time solution for computing factors having an exponent at least 2 in a string on an infinite alphabet.

Then it shows how to design an algorithm to compute the maximal exponent of factors of an overlap-free string. The algorithm runs in linear-time on a fixed-size alphabet, while a naive solution of the question would run in cubic time. The solution for non overlap-free strings derives from previous algorithms to compute all maximal periodicities, also called runs, occurring in the string.

On the combinatorial aspect of the computation we show there is a linear number of maximal-exponent factors in an overlap-free string. The algorithm can be adapted to locate them all in linear time as well.

Biography

Prof. Maxime Crochemore received his PhD in 1978 and his Doctorat d'état (DSc) in 1983 at the University of Rouen. He got his first professorship position at the University of Paris-Nord in 1985 where he acted as President of the Department of Mathematics and Computer Science for two years. He became professor at the University Paris 7 in 1989 and was involved in the creation of the University of Marne-la-Vallée where he is Professor, Emeritus from 2007. He also created the Computer Science research laboratory of this university in 1991 and was the director until 2005. He was Deputy Scientific Director of the Information and Communication Department of CNRS from 2004 to 2006. He was Senior Research Fellow from 2002 to 2007 and is presently Professor at King's College London.

Prof. Crochemore's research interests are in the design and analysis of algorithms. His major achievements are on string algorithms, which includes pattern matching, text indexing, coding, and text compression. He also works on the combinatorial background of these subjects and on their applications to bio-informatics. He has co-authored several textbooks on algorithms and published more than 200 articles, among which 144 are listed on the DBLP Bibliography Server as of February 2011.

He has been the recipient of several French grants on string algorithms and bio-informatics. He participated in a good number of international projects on algorithms and supervised to completion more than twenty PhD students.