Abstract
We consider the problem of computing a solid cover of an indeterminate string. An indeterminate string may contain non-solid symbols, each of which specifies a subset of the alphabet that could be present at the corresponding position. We also consider covering partial words, which are a special case of indeterminate strings where each non-solid symbol is a don’t care symbol. We prove that both indeterminate string covering problem and partial word covering problem are NP-complete for binary alphabet and show that both problems are fixed-parameter tractable with respect to \(k\), the number of non-solid symbols. For the indeterminate string covering problem we obtain a \(2^{\mathcal {O}(k\log k)} + n k^{\mathcal {O}(1)}\)-time algorithm. For the partial word covering problem we obtain a \(2^{\mathcal {O}(\sqrt{k}\log k)} + nk^{\mathcal {O}(1)}\)-time algorithm. We prove that, unless the Exponential Time Hypothesis is false, no \(2^{o(\sqrt{k})} n^{\mathcal {O}(1)}\)-time solution exists for this problem, which shows that our algorithm for this case is close to optimal. We also present an algorithm for both problems which is feasible in practice.
Tomasz Kociumaka: Supported by Polish budget funds for science in 2013-2017 as a research project under the ’Diamond Grant’ program.
Jakub Radoszewski: The author receives financial support of Foundation for Polish Science.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Abrahamson, K.R.: Generalized string matching. SIAM Journal on Computing 16(6), 1039–1051 (1987)
Antoniou, P., Crochemore, M., Iliopoulos, C.S., Jayasekera, I., Landau, G.M.: Conservative string covering of indeterminate strings. In: Holub, J., Žďárek, J. (eds.) Prague Stringology Conference 2008, pp. 108–115. Czech Technical University, Prague (2008)
Apostolico, A., Ehrenfeucht, A.: Efficient detection of quasiperiodicities in strings. Theoretical Computer Science 119(2), 247–265 (1993)
Apostolico, A., Farach, M., Iliopoulos, C.S.: Optimal superprimitivity testing for strings. Information Processessing Letters 39(1), 17–20 (1991)
Bari, M.F., Rahman, M.S., Shahriyar, R.: Finding all covers of an indeterminate string in \(O(n)\) time on average. In: Holub, J., Žďárek, J. (eds.) Prague Stringology Conference 2009, pp. 263–271. Czech Technical University, Prague (2009)
Blanchet-Sadri, F.: Algorithmic Combinatorics on Partial Words. Chapman & Hall/CRC Press, Boca Raton (2008)
Breslauer, D.: An on-line string superprimitivity test. Information Processing Letters 44(6), 345–347 (1992)
Crochemore, M., Hancart, C., Lecroq, T.: Algorithms on Strings. Cambridge University Press (2007)
Fischer, M.J., Paterson, M.S.: String matching and other products. In: Karp, R.M. (ed.) Complexity of Computation. SIAM-AMS Proceedings, vol. 7, pp. 113–125. AMS, Providence (1974)
Holub, J., Smyth, W.F., Wang, S.: Fast pattern-matching on indeterminate strings. Journal of Discrete Algorithms 6(1), 37–50 (2008)
Iliopoulos, C.S., Mohamed, M., Mouchard, L., Perdikuri, K., Smyth, W.F., Tsakalidis, A.K.: String regularities with don’t cares. Nordic Journal of Computing 10(1), 40–51 (2003)
Iliopoulos, C.S., Moore, D., Park, K.: Covering a string. Algorithmica 16(3), 288–297 (1996)
Impagliazzo, R., Paturi, R.: On the complexity of \(k\)-SAT. Journal of Computer and System Sciences 62(2), 367–375 (2001)
Impagliazzo, R., Paturi, R., Zane, F.: Which problems have strongly exponential complexity? Journal of Computer and System Sciences 63(4), 512–530 (2001)
Indyk, P.: Faster algorithms for string matching problems: Matching the convolution bound. In: 39th Annual Symposium on Foundations of Computer Science, pp. 166–173. IEEE Computer Society, Los Alamitos (1998)
Kalai, A.: Efficient pattern-matching with don’t cares. In: Eppstein, D. (ed.) 13th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 655–656. SIAM, Philadelpha (2002)
Kociumaka, T., Kubica, M., Radoszewski, J., Rytter, W., Waleń, T.: A linear time algorithm for seeds computation. In: Rabani, Y. (ed.) 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1095–1112. SIAM, Philadelpha (2012)
Li, Y., Smyth, W.F.: Computing the cover array in linear time. Algorithmica 32(1), 95–106 (2002)
Lokshtanov, D., Marx, D., Saurabh, S.: Lower bounds based on the Exponential Time Hypothesis. Bulletin of the EATCS 105, 41–72 (2011)
Moore, D., Smyth, W.F.: Computing the covers of a string in linear time. In: Sleator, D.D. (ed.) 5th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 511–515. SIAM, Philadelpha (1994)
Muthukrishnan, S., Palem, K.V.: Non-standard stringology: algorithms and complexity. In: 26th Annual ACM Symposium on Theory of Computing, pp. 770–779. ACM, New York (1994)
Smyth, W.F., Wang, S.: An adaptive hybrid pattern-matching algorithm on indeterminate strings. International Journal of Foundations of Computer Science 20(6), 985–1004 (2009)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Crochemore, M., Iliopoulos, C.S., Kociumaka, T., Radoszewski, J., Rytter, W., Waleń, T. (2014). Covering Problems for Partial Words and for Indeterminate Strings. In: Ahn, HK., Shin, CS. (eds) Algorithms and Computation. ISAAC 2014. Lecture Notes in Computer Science(), vol 8889. Springer, Cham. https://doi.org/10.1007/978-3-319-13075-0_18
Download citation
DOI: https://doi.org/10.1007/978-3-319-13075-0_18
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-13074-3
Online ISBN: 978-3-319-13075-0
eBook Packages: Computer ScienceComputer Science (R0)