2026-07-24T19:05:04Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10490 2024-03-06T10:45:52Z ddc:004 open_access

Dichotomic Selection on Words: A Probabilistic Analysis Akhavi, Ali Clément, Julien Darthenay, Dimitri Lhote, Loïck Vallée, Brigitte dichotomic selection text algorithms analysis of algorithms average case analysis of algorithms trie suffix array lcp-array information theory numeration process sources entropy coincidence analytic combinatorics depoissonization techniques The paper studies the behaviour of selection algorithms that are based on dichotomy principles. On the entry formed by an ordered list L and a searched element x not in L, they return the interval of the list L the element x belongs to. We focus here on the case of words, where dichotomy principles lead to a selection algorithm designed by Crochemore, Hancart and Lecroq, which appears to be "quasi-optimal". We perform a probabilistic analysis of this algorithm that exhibits its quasi-optimality on average. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ali Akhavi and Julien Clément and Dimitri Darthenay and Loïck Lhote and Brigitte Vallée 2019 Is Part Of LIPIcs, Volume 128, 30th Annual Symposium on Combinatorial Pattern Matching (CPM 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CPM.2019.19 urn:nbn:de:0030-drops-104903 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2019.19 eng https://creativecommons.org/licenses/by/3.0/legalcode