论文标题
符合DAG的字符串算法：Funnels及其他
Parameterized Algorithms for String Matching to DAGs: Funnels and Beyond
论文作者
论文摘要
字符串与标记图（SMLG）的字符串匹配问题要求在标记的图形$ g =（v，e）$中找到其拼写匹配的所有路径，其拼写与输入字符串$ s \ inσ^m $相匹配。 SMLG可以用二次$ O（m | e |）$ time [Amir等，Jalg]解决，这被Seth [Equi等人，ICALP 2019]的最新下限证明是最佳的。下联界指出，即使仅限于定向的无环图（DAG），也不存在强大的亚次级时间算法。 在这项工作中，我们介绍了DAG中SMLG的第一个参数化算法。我们的参数捕获了$ g $的拓扑结构。我们所有的结果均来自Knuth-Morris-Pratt算法[Park and Kim，CPM 1995]的概括，该算法与前缀不可抵押的匹配次数成正比作用。 为了获得$ g $的拓扑结构中的参数化，我们首先研究了一个名为Funnels [Millani等人，JCO]的特殊类，并将其推广到$ k $ -Funnnels和类$ ST_K $。我们对漏斗及其概括提出了几种新颖的特征和算法贡献。
The problem of String Matching to Labeled Graphs (SMLG) asks to find all the paths in a labeled graph $G = (V, E)$ whose spellings match that of an input string $S \in Σ^m$. SMLG can be solved in quadratic $O(m|E|)$ time [Amir et al., JALG], which was proven to be optimal by a recent lower bound conditioned on SETH [Equi et al., ICALP 2019]. The lower bound states that no strongly subquadratic time algorithm exists, even if restricted to directed acyclic graphs (DAGs). In this work we present the first parameterized algorithms for SMLG in DAGs. Our parameters capture the topological structure of $G$. All our results are derived from a generalization of the Knuth-Morris-Pratt algorithm [Park and Kim, CPM 1995] optimized to work in time proportional to the number of prefix-incomparable matches. To obtain the parameterization in the topological structure of $G$, we first study a special class of DAGs called funnels [Millani et al., JCO] and generalize them to $k$-funnels and the class $ST_k$. We present several novel characterizations and algorithmic contributions on both funnels and their generalizations.
