On maximal unbordered factors

DOI10.1007/978-3-319-19929-0_29MaRDI QIDQ2942272zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Alexander Loptev, Gregory Kucherov, Tatiana Starikovskaya

Publication date 20 August 2015

Published in Combinatorial Pattern Matching (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1504.07406

Mathematics Subject Classification ID

Combinatorics on words (68R15) Algorithms on strings (68W32)

Abstract: Given a string $S$ of length $n$, its maximal unbordered factor is the longest factor which does not have a border. In this work we investigate the relationship between $n$ and the length of the maximal unbordered factor of $S$. We prove that for the alphabet of size $sigmage5$ the expected length of the maximal unbordered factor of a string of length~$n$ is at least $0.99n$ (for sufficiently large values of $n$). As an application of this result, we propose a new algorithm for computing the maximal unbordered factor of a string.

Recommendations

• Unbordered partial words
• The Ehrenfeucht-Silberger problem
• The Ehrenfeucht-Silberger Problem

Cites work

• scientific article; zbMATH DE number 1874382 (Why is no real title available?)
• A note on bifix-free sequences (Corresp.)
• Border array on bounded alphabet
• Counting distinct strings
• Internal pattern matching queries in a text and applications
• Linear computation of unbordered conjugate on unordered alphabet
• On the number of prefix and border tables
• Periodicity and unbordered segments of words
• Relationship between the period of a finite word and the length of its unbordered segments
• The Ehrenfeucht-Silberger problem
• The longest common extension problem revisited and applications to approximate string searching
• Une caractérisation des mots périodiques
• Validating the Knuth-Morris-Pratt failure function, fast and online

Cited in

(4)

• Longest unbordered factor in quasilinear time
• The Ehrenfeucht-Silberger Problem
• Computing the Longest Unbordered Substring
• Linear computation of unbordered conjugate on unordered alphabet

This page was built for publication: On maximal unbordered factors

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2942272)