On extended special factors of a word

Panagiotis Charalampopoulos, Maxime Crochemore, Solon P. Pissis*

*Corresponding author for this work

Research output: Chapter in Book / Report / Conference proceedingConference contributionAcademicpeer-review

Abstract

An extended special factor of a word x is a factor of x whose longest infix can be extended by at least two distinct letters to the left or to the right and still occur in x. It is called extended bispecial if it can be extended in both directions and still occur in x. Let ρ(n) be the maximum number of extended bispecial factors over all words of length n. Almirantis et al. have shown that 2n - 6≤ ρ(n)≤ 3n-4 [WABI 2017]. In this article, we show that there is no constant c <3 such that ρ(n)≤cn. We then exploit the connection between extended special factors and minimal absent words to construct a data structure for computing minimal absent words of a specific length in optimal time for integer alphabets generalising a result by Fujishige et al. [MFCS 2016]. As an application of our data structure, we show how to compare two words over an integer alphabet in optimal time improving on another result by Charalampopoulos et al. [Inf. Comput. 2018].

Original languageEnglish
Title of host publicationString Processing and Information Retrieval - 25th International Symposium, SPIRE 2018, Proceedings
EditorsTravis Gagie, Alistair Moffat, Gonzalo Navarro, Ernesto Cuadros-Vargas
PublisherSpringer Verlag
Pages131-138
Number of pages8
ISBN (Print)9783030004781
DOIs
Publication statusPublished - 1 Jan 2018
Externally publishedYes
Event25th International Symposium on String Processing and Information Retrieval, SPIRE 2018 - Lima, Peru
Duration: 9 Oct 201811 Oct 2018

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume11147 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference25th International Symposium on String Processing and Information Retrieval, SPIRE 2018
CountryPeru
CityLima
Period9/10/1811/10/18

Keywords

  • Minimal absent words
  • Special factors
  • String algorithms

Fingerprint

Dive into the research topics of 'On extended special factors of a word'. Together they form a unique fingerprint.

Cite this