TY - GEN

T1 - On extended special factors of a word

AU - Charalampopoulos, Panagiotis

AU - Crochemore, Maxime

AU - Pissis, Solon P.

PY - 2018/1/1

Y1 - 2018/1/1

N2 - 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].

AB - 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].

KW - Minimal absent words

KW - Special factors

KW - String algorithms

UR - http://www.scopus.com/inward/record.url?scp=85054880953&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85054880953&partnerID=8YFLogxK

U2 - 10.1007/978-3-030-00479-8_11

DO - 10.1007/978-3-030-00479-8_11

M3 - Conference contribution

AN - SCOPUS:85054880953

SN - 9783030004781

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 131

EP - 138

BT - String Processing and Information Retrieval - 25th International Symposium, SPIRE 2018, Proceedings

A2 - Gagie, Travis

A2 - Moffat, Alistair

A2 - Navarro, Gonzalo

A2 - Cuadros-Vargas, Ernesto

PB - Springer Verlag

T2 - 25th International Symposium on String Processing and Information Retrieval, SPIRE 2018

Y2 - 9 October 2018 through 11 October 2018

ER -