2026-07-28T07:10:26Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:20438 2024-11-27T23:17:31Z ddc:004 open_access

Maximal Number of Subword Occurrences in a Word Fang, Wenjie Subword occurrence subword entropy enumeration periodic words We consider the number of occurrences of subwords (non-consecutive sub-sequences) in a given word. We first define the notion of subword entropy of a given word that measures the maximal number of occurrences among all possible subwords. We then give upper and lower bounds of minimal subword entropy for words of fixed length in a fixed alphabet, and also showing that minimal subword entropy per letter has a limit value. A better upper bound of minimal subword entropy for a binary alphabet is then given by looking at certain families of periodic words. We also give some conjectures based on experimental observations. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Wenjie Fang 2024 Is Part Of LIPIcs, Volume 302, 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.AofA.2024.3 urn:nbn:de:0030-drops-204387 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2024.3 eng https://creativecommons.org/licenses/by/4.0/legalcode