Faster Approximate String Matching for Short Patterns (2008)
We study the classical approximate string matching problem, that is, given strings $P$ and $Q$ and an error threshold $k$, find all ending positions of substrings of $Q$ whose edit distance to $P$ is...
Pattern Matching in Trees and Strings (2007)
We study the design of efficient algorithms for combinatorial pattern matching. More concretely, we study algorithms for tree matching, string matching, and string matching in compressed texts.
Pattern Matching in Trees and Strings (2007)
We study the design of efficient algorithms for combinatorial pattern matching. More concretely, we study algorithms for tree matching, string matching, and string matching in compressed texts.
Fast evaluation of union-intersection expressions (2007)
Bille, Philip, Pagh, Anna, Pagh, Rasmus
We show how to represent sets in a linear space data structure such that expressions involving unions and intersections of sets can be computed in a worst-case efficient way. This problem has...
Bille, Philip, Fagerberg, Rolf, Goertz, Inge Li
We study the approximate string matching and regular expression matching problem for the case when the text to be searched is compressed with the Ziv-Lempel adaptive dictionary compression schemes....
The Tree Inclusion Problem: In Linear Space and Faster (2006)
Bille, Philip, Goertz, Inge Li
Given two rooted, ordered, and labeled trees $P$ and $T$ the tree inclusion problem is to determine if $P$ can be obtained from $T$ by deleting nodes in $T$. This problem has recently been recognized...
New Algorithms for Regular Expression Matching (2006)
In this paper we revisit the classical regular expression matching problem, namely, given a regular expression $R$ and a string $Q$, decide if $Q$ matches one of the strings specified by $R$. Let $m$...
Matching Subsequences in Trees (2005)
Bille, Philip, Goertz, Inge Li
Given two rooted, labeled trees $P$ and $T$ the tree path subsequence problem is to determine which paths in $P$ are subsequences of which paths in $T$. Here a path begins at the root and ends at a...
Fast and Compact Regular Expression Matching (2005)
Bille, Philip, Farach-Colton, Martin
We study 4 problems in string matching, namely, regular expression matching, approximate regular expression matching, string edit distance, and subsequence indexing, on a standard word RAM model of...
Tree Edit Distance, Alignment Distance and Inclusion (2003)
We survey the problem of comparing labeled trees based on simple local operations of deleting, inserting and relabeling nodes. These operations lead to the tree edit distance, alignment distance and...