2026-07-22T12:34:48Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:4922 2024-03-06T10:35:33Z ddc:004 open_access

Pattern Matching with Variables: Fast Algorithms and New Hardness Results Fernau, Henning Manea, Florin Mercas, Robert Schmid, Markus L. combinatorial pattern matching combinatorics on words patterns with variables ${cal NP}$-complete string problems A pattern (i. e., a string of variables and terminals) maps to a word, if this is obtained by uniformly replacing the variables by terminal words; deciding this is NP-complete. We present efficient algorithms\footnote{The computational model we use is the standard unit-cost RAM with logarithmic word size. Also, all logarithms appearing in our time complexity evaluations are in base 2.} that solve this problem for restricted classes of patterns. Furthermore, we show that it is NP-complete to decide, for a given number k and a word w, whether w can be factorised into k distinct factors; this shows that the injective version (i.e., different variables are replaced by different words) of the above matching problem is NP-complete even for very restricted cases. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Henning Fernau and Florin Manea and Robert Mercas and Markus L. Schmid 2015 Is Part Of LIPIcs, Volume 30, 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2015.302 urn:nbn:de:0030-drops-49220 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2015.302 eng https://creativecommons.org/licenses/by/3.0/legalcode