Linear Pattern Matching Algorithms

By P. Weiner. 1973

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Algorithms & Complexity

Citations in the corpus

Deduplicating Training Data Makes Language Models Better (2021, background): “A sufﬁx array (Manber and Myers, 1993) is a representation of a sufﬁx tree (Weiner, 1973) that can be constructed in linear time in (cid:107)S(cid:107) (Kärkkäinen and Sanders, 2003) and enables efﬁcient computation of many substring queries; in particular, they allow us to identify duplicated…”
Replacing suffix trees with enhanced suffix arrays (2004, unknown): “The suffix tree of a sequence S is an index structure that can be computed and stored in O(n) time and space [32], where n= |S|.”
Space efficient linear time construction of suffix arrays (2003, background): “In fact, it is simpler than linear time suffix tree construction algorithms for fixed size alphabets [17–19].”
Compressed Suffix Trees with Full Functionality (2007, background): “A suffix tree of a string can be constructed in linear time in the string length [28, 21, 27, 5].”
Spatio-Temporal Analysis of Team Sports (2016, methodology): “A suffix tree [87] was used as a data structure D to store sequences of passes between individual players.”
Graph kernels for chemical informatics (2005, methodology): “However, using a suffix tree data structure [Ukkonen, 1995, Weiner, 1973] as also proposed in [Leslie et al., 2002, Vishwanathan and Smola, 2003], allows us to compute each of the proposed kernels in time O(d(n 1 m 1 + n 2 m 2 )), where d is the depth of the search and n i (resp. m i ) the number…”
Byte Pair Encoding: a Text Compression Scheme That Accelerates Pattern Matching (1999, methodology): “In case that we have enough storage devices and the texts to be stored are almost static, we may construct such data structures as inverted- les [18], su x-trees [40, 30, 39], or su x-arrays [29] in order to nd a pattern very quickly.”
Fast Kernels for String and Tree Matching (2002, background): “Given a string t and a suffix tree S(x), we can decide if t ∈ words(S(x)) in O(|t|) time by just walking down the corresponding edges of S(x) (Weiner, 1973).”
SeqAn An efficient, generic C++ library for sequence analysis (2008, background): “To find MUMs MUMmer builds a suffix tree [41] of a reference sequence and streams one or more query sequences against it.”
Honeycomb (2004, methodology): “Several algorithms have been proposed to build suffix trees in linear time [8][9]; our implementation uses Ukkonen’s algorithm[10].”
Linear work suffix array construction (2006, background): “It can be constructed in linear time in the length of the string [Weiner 1973; McCreight 1976; Ukkonen 1995; Farach 1997; Farach-Colton et al. 2000].”
STREME: Accurate and versatile sequence motif discovery (2020, methodology): “, Weeder [10], HOMER [5], STEME [12]), STREME makes use of a data structure called a generalized suffix tree [18].”
High-throughput sequence alignment using Graphics Processing Units (2007, background): “The suffix tree [12] for string S is a tree that encodes every suffix of S with a unique path from the root to a leaf.”
Compressed full-text indexes (2007, background): “Moreover, they can be built in O(n) time [Weiner 1973; McCreight 1976; Ukkonen 1995; Farach 1997].”