Laboratoire
Équipes
Membres
Événements
Info scientifique
Info. pratiques
Intranet LIGM
Retour à l'accueil
Séminaire Algo - Shiho Sugimoto
Séminaire Algo - Shiho Sugimoto Il y a: 1 year ![]() Shiho Sugimoto Computing palindromic factorizations and palindromic covers on-line Salle de séminaire (4B05R) - Bâtiment Copernic Abstract: A palindromic factorization of a string w is a factorization of w consisting only of palindromic substrings of w. In this paper, we present an on-line O(n log n)-time O(n)-space algorithm to compute smallest palindromic factorizations of all prefixes of w, where n is the length of a given string w. We then show how to extend this algorithm to compute smallest maximal palindromic factorizations of all prefixes of w, consisting only of maximal palindromes (non-extensible palindromic substring) of each prefix, in O(n log n) time and O(n) space, in an on-line manner. We also present an on-line O(n)-time O(n)-space algorithm to compute a smallest palindromic cover of w. |