On maximal unbordered factors

DOI10.1007/978-3-319-19929-0_29zbMATH Open1397.68150DBLPconf/cpm/LoptevKS15arXiv1504.07406OpenAlexW2146315056WikidataQ58064460 ScholiaQ58064460MaRDI QIDQ2942272FDOQ2942272

Authors: Alexander Loptev, Gregory Kucherov, Tatiana Starikovskaya 

Publication date: 20 August 2015

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

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.

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

Recommendations

• Maximal unbordered factors of random strings
• Maximal unbordered factors of random strings
• Unbordered partial words
• The Ehrenfeucht-Silberger problem
• The Ehrenfeucht-Silberger Problem

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (5)

• Title not available (Why is that?)
• Computing the Longest Unbordered Substring
• Linear computation of unbordered conjugate on unordered alphabet
• The Ehrenfeucht-Silberger Problem
• Maximal unbordered factors of random strings

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)