文章基本信息

标题：On Indeterminate Strings Matching
本地全文：下载
作者：PaweÅ, Gawrychowski ; Samah Ghazawi ; Gad M. Landau 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：161
页码：14:1-14:14
DOI：10.4230/LIPIcs.CPM.2020.14
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：Given two indeterminate equal-length strings p and t with a set of characters per position in both strings, we obtain a determinate string p_w from p and a determinate string t_w from t by choosing one character per position. Then, we say that p and t match when p_w and t_w match for some choice of the characters. While the most standard notion of a match for determinate strings is that they are simply identical, in certain applications it is more appropriate to use other definitions, with the prime examples being parameterized matching, order-preserving matching, and the recently introduced Cartesian tree matching. We provide a systematic study of the complexity of string matching for indeterminate equal-length strings, for different notions of matching. We use n to denote the length of both strings, and r to be an upper-bound on the number of uncertain characters per position. First, we provide the first polynomial time algorithm for the Cartesian tree version that runs in deterministic ð'ª(nlogÂ² n) and expected ð'ª(nlog nlog log n) time using ð'ª(nlog n) space, for constant r. Second, we establish NP-hardness of the order-preserving version for r=2, thus solving a question explicitly stated by Henriques et al. [CPM 2018], who showed hardness for r=3. Third, we establish NP-hardness of the parameterized version for r=2. As both parameterized and order-preserving indeterminate matching reduce to the standard determinate matching for r=1, this provides a complete classification for these three variants.
关键词：string matching; indeterminate strings; Cartesian trees; order-preserving matching; parameterized matching