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, Tomasz Waleń

*Corresponding author for this work

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

Abstract

A word of the form WW for some word (formula presented) is called a square, where \varSigma is an alphabet. A partial word is a word possibly containing holes (also called don’t cares). The hole is a special symbol which matches (agrees with) any symbol from. 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. We denote by psquares (T) the number of non-equivalent p-squares which are factors of a partial word T. Let (formula presented) be the maximum value of psquares (T) over all partial words of length n with at most k holes. We show asymptotically tight bounds: (formula presented) for some constants c:1,c_2>0. We also present an algorithm that computes psquares (T)(formula presented) time for a partial word T of length n with k holes. In particular, our algorithm runs in linear time for (formula presented) and its time complexity near-matches the maximum number of non-equivalent p-square factors in a partial word.

Original languageEnglish
Title of host publicationComputing and Combinatorics - 23rd International Conference, COCOON 2017, Proceedings
EditorsYixin Cao, Jianer Chen
PublisherSpringer Verlag
Pages99-111
Number of pages13
ISBN (Print)9783319623887
DOIs
Publication statusPublished - 1 Jan 2017
Externally publishedYes
Event23rd International Conference on Computing and Combinatorics, COCOON 2017 - Hong Kong, China
Duration: 3 Aug 20175 Aug 2017

Publication series

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

Conference

Conference23rd International Conference on Computing and Combinatorics, COCOON 2017
Country/TerritoryChina
CityHong Kong
Period3/08/175/08/17

Funding

P. Charalampopoulos—Supported by the Graduate Teaching Scholarship scheme of the Department of Informatics at King’s College London. T. Kociumaka—Supported by Polish budget funds for science in 2013–2017 as a research project under the ’Diamond Grant’ program. J. Radoszewski, W. Rytter and T. Waleń—Supported by the Polish National Science Center, grant no. 2014/13/B/ST6/00770.

FundersFunder number
Polish National Science Center2014/13/B/ST6/00770

    Fingerprint

    Dive into the research topics of 'Efficient enumeration of non-equivalent squares in partial words with few holes'. Together they form a unique fingerprint.

    Cite this