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 -