The normalized substring complexity \(\delta\) of a string is defined as \(\max_k \{c[k]/k\}\), where \(c[k]\) is the number of distinct substrings of length \(k\). This simply defined measure has recently attracted attention due to its established relationship to popular string compression algorithms. We consider the problem of computing \(\delta\) online, when the string is provided from a stream. The work relies on a combination of results of word combinatorics, string algorithms, data structures and computational geometry.
Localisation
Salle de séminaire 4B125 (bâtiment Copernic)
5 Boulevard Descartes 77420 Champs-sur-Marne