Efficient enumeration of non-equivalent squares in partial words with few holes

Panagiotis Charalampopoulos (), Maxime Crochemore (), Costas S. Iliopoulos (), Tomasz Kociumaka (), Solon P. Pissis (), Jakub Radoszewski (), Wojciech Rytter () and Tomasz Waleń ()
Additional contact information
Panagiotis Charalampopoulos: King’s College London
Maxime Crochemore: King’s College London
Costas S. Iliopoulos: King’s College London
Tomasz Kociumaka: University of Warsaw
Solon P. Pissis: King’s College London
Jakub Radoszewski: University of Warsaw
Wojciech Rytter: University of Warsaw
Tomasz Waleń: University of Warsaw

Journal of Combinatorial Optimization, 2019, vol. 37, issue 2, No 7, 522 pages

Abstract: Abstract A word of the form WW for some word $$W\in \varSigma ^*$$ W ∈ Σ ∗ is called a square. A partial word is a word possibly containing holes (also called don’t cares). The hole is a special symbol $$\lozenge \notin \varSigma $$ ◊ ∉ Σ which matches any symbol from $$\varSigma \cup \{\lozenge \}$$ Σ ∪ { ◊ } . A p-square is a partial word matching at least one square WW without holes. Two p-squares are called equivalent if they match the same set of squares. A p-square is called here unambiguous if it matches exactly one square WW without holes. Such p-squares are natural counterparts of classical squares. Let $$\mathrm {PSQUARES}_k(n)$$ PSQUARES k ( n ) and $$\mathrm {USQUARES}_k(n)$$ USQUARES k ( n ) be the maximum number of non-equivalent p-squares and non-equivalent unambiguous p-squares in T over all partial words T of length n with at most k holes. We show asymptotically tight bounds: $$\begin{aligned} \mathrm {PSQUARES}_k(n) = \varTheta (\min (nk^2,\, n^2)),\ \ \mathrm {USQUARES}_k(n) = \varTheta (nk). \end{aligned}$$ PSQUARES k ( n ) = Θ ( min ( n k 2 , n 2 ) ) , USQUARES k ( n ) = Θ ( n k ) . We present an algorithm that reports all non-equivalent p-squares in $$\mathcal {O}(nk^3)$$ O ( n k 3 ) time for a partial word of length n with k holes, for an integer alphabet. In particular, it runs in linear time for $$k=\mathcal {O}(1)$$ k = O ( 1 ) and its time complexity near-matches the asymptotic bound for $$\mathrm {PSQUARES}_k(n)$$ PSQUARES k ( n ) . We also show an $$\mathcal {O}(n)$$ O ( n ) -time algorithm that reports all non-equivalent p-squares of a given length. The paper is a full and improved version of Charalampopoulos et al. (in Cao Y, Chen Y (eds) Proceedings of the 23rd international conference on computing and combinatorics, COCOON 2017; Springer, 2017).

Keywords: Partial word; Square in a word; Approximate period; Lyndon word (search for similar items in EconPapers)
Date: 2019
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-018-0300-z Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:37:y:2019:i:2:d:10.1007_s10878-018-0300-z

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-018-0300-z

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().