Bollobás, B;
Letzter, S;
(2018)
Longest common extension.
European Journal of Combinatorics
, 68
pp. 242-248.
10.1016/j.ejc.2017.07.019.
Preview |
Text
longest-ext-23-May.pdf - Accepted Version Download (248kB) | Preview |
Abstract
Given a word w of length n and i, j ∈ [n], the longest common extension is the longest substring starting at both i and j. In this note we estimate the average length of the longest common extension over all words w and all pairs (i, j), as well as the typical maximum length of the longest common extension. We also consider a variant of this problem, due to Blanchet-Sadri and Lazarow, in which the word is allowed to contain ‘holes’, which are special symbols functioning as ‘jokers’, i.e. are considered to be equal to any character. In particular, we estimate the average longest common extension over all words w with a small number of holes, extending a result by Blanchet-Sadri, Harred and Lazarow, and prove a similar result for words with holes appearing randomly.
| Type: | Article |
|---|---|
| Title: | Longest common extension |
| Open access status: | An open access version is available from UCL Discovery |
| DOI: | 10.1016/j.ejc.2017.07.019 |
| Publisher version: | https://doi.org/10.1016/j.ejc.2017.07.019 |
| Language: | English |
| Additional information: | This version is the author accepted manuscript. For information on re-use, please refer to the publisher's terms and conditions. |
| UCL classification: | UCL UCL > Provost and Vice Provost Offices UCL > Provost and Vice Provost Offices > UCL BEAMS UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Maths and Physical Sciences UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Maths and Physical Sciences > Dept of Mathematics |
| URI: | https://discovery.ucl.ac.uk/id/eprint/10107278 |
Archive Staff Only
 |
View Item |
