- Fast Algorithms for Exact String Matching
2015/09/30 by Srikrishnan Divakaran, Divakaran, Srikrishnan · 1 voice · 1 citation
Biochemistry, Genetics and Molecular Biology · Computer Science · Mathematics · #Algorithm #Algorithms and Data Compression #Alphabet #Artificial intelligence #Combinatorics #Computer science #DNA and Biological Computing #Data structure #Mathematics #Omega #Pattern matching #Physics #String (physics) #String searching algorithm #Substring #cs.DS #semigroups and automata theory
- A simple parallel cartesian tree algorithm and its application to parallel suffix tree construction
2014/10/03 by Julian Shun, Guy E. Blelloch · 1 citation
Computer Science · Biochemistry, Genetics and Molecular Biology · Mathematics · #Algorithms and Data Compression #Network Packet Processing and Optimization #Genomics and Phylogenetic Studies #Suffix array #Suffix tree #Generalized suffix tree #Trie #Algorithm #Parallel algorithm #Hash table #String (physics) #Suffix #Tree (set theory) #Data structure #Perfect hash function #String searching algorithm #Computer science #Time complexity #Mathematics #Prefix #Combinatorics #Hash function
- Order Preserving Matching
2013/02/17 by Jinil Kim, Jin-Il Kim, Kim, Jinil +14 · 2 citations
Computer Science · Mathematics · #Algorithm #Algorithms and Data Compression #Approximate string matching #Artificial intelligence #Combinatorics #Computer science #Data Structures and Algorithms (cs.DS) #Data structure #FOS: Computer and information sciences #Matching (statistics) #Mathematics #Music and Audio Processing #Natural Language Processing Techniques #Order (exchange) #Pattern matching #Prefix #Representation (politics) #Statistics #String (physics) #String searching algorithm #Substring #Suffix tree #Theoretical computer science #Trie #cs.DS
- Faster suffix sorting
2007/07/31 by Niklas Larsson, N. Jesper Larsson, Kunihiko Sadakane · 2 citations
Computer Science · Mathematics · #Algorithm #Algorithms and Data Compression #Artificial intelligence #Combinatorics #Compressed suffix array #Computer science #Data structure #Lexicographical order #Mathematics #Natural Language Processing Techniques #Network Packet Processing and Optimization #Pattern matching #Robustness (evolution) #Sorting #String searching algorithm #Suffix array #Theoretical computer science #Time complexity
- LZgrep: a Boyer-Moore string matching tool for Ziv-Lempel compressed text
2005/01/01 by Gonzalo Navarro, Jorma Tarhio · 1 citation
Computer Science · Mathematics · #Algorithm #Algorithms and Data Compression #Approximate string matching #Computer science #Matching (statistics) #Mathematics #Network Packet Processing and Optimization #Pattern matching #Programming language #Simple (philosophy) #Software #String (physics) #String searching algorithm #Theoretical computer science #Unix #Web Data Mining and Analysis
- Mutable strings in Java: design, implementation and lightweight text-search algorithms
2004/10/26 by Paolo Boldi, Sebastiano Vigna · 1 citation
Computer Science · Mathematics · #Algorithm #Approximate string matching #Artificial intelligence #Caching and Content Delivery #Computer science #Data structure #Java #Mathematics #Network Packet Processing and Optimization #Pattern matching #Programming language #String (physics) #String metric #String searching algorithm #Theoretical computer science #Unicode #Web Data Mining and Analysis
- Replacing suffix trees with enhanced suffix arrays
2004/02/28 by Mohamed Abouelhoda, Mohamed Ibrahim Abouelhoda, Stefan Kurtz +1 · 5 citations
Biochemistry, Genetics and Molecular Biology · Computer Science · Mathematics · #Algorithm #Algorithms and Data Compression #Bottleneck #Combinatorics #Compressed suffix array #Computer science #Data structure #Generalized suffix tree #Genomics and Phylogenetic Studies #Mathematics #RNA and protein synthesis mechanisms #String (physics) #String searching algorithm #Suffix #Suffix array #Suffix tree #Theoretical computer science #Tree (set theory)
- Distinguishing string selection problems
2003/04/24 by J. Kevin Lanctot, Ming Li, Bin Ma +2 · 3 citations
Biochemistry, Genetics and Molecular Biology · Computer Science · Mathematics · #Advanced biosensing and bioanalysis techniques #Algorithm #Algorithms and Data Compression #Approximate string matching #Artificial intelligence #Combinatorics #Commentz-Walter algorithm #Computer science #DNA and Biological Computing #Discrete mathematics #Edit distance #Hamming distance #Mathematics #Pattern matching #Set (abstract data type) #String (physics) #String metric #String searching algorithm #Substring #Time complexity
- Optimal suffix tree construction with large alphabets
2002/11/22 by Martı́n Farach-Colton · 6 citations
Computer Science · Mathematics · #Algorithms and Data Compression #Machine Learning and Algorithms #Advanced Image and Video Retrieval Techniques #Suffix tree #Generalized suffix tree #Compressed suffix array #Combinatorics #Suffix #Upper and lower bounds #String (physics) #Mathematics #Data structure #Sorting #Integer (computer science) #String searching algorithm #Time complexity #Discrete mathematics #Tree (set theory) #Suffix array #Alphabet #Closing (real estate) #Computer science #Algorithm
- The Enhanced Suffix Array and Its Applications to Genome Analysis
2002/01/01 by Mohamed Abouelhoda, Mohamed Ibrahim Abouelhoda, Stefan Kurtz +1 · 6 citations
Biochemistry, Genetics and Molecular Biology · Computer Science · Mathematics · #Algorithm #Algorithms and Data Compression #Artificial intelligence #Combinatorics #Compressed suffix array #Computer science #Data structure #Generalized suffix tree #Genomics and Phylogenetic Studies #Mathematics #Pattern matching #Programming language #RNA and protein synthesis mechanisms #String (physics) #String searching algorithm #Suffix #Suffix array #Suffix tree #Theoretical computer science #Tree (set theory) #Tree traversal
- A guided tour to approximate string matching
2001/03/01 by Gonzalo Navarro · 1 citation
Computer Science · Biochemistry, Genetics and Molecular Biology · Mathematics · #Algorithms and Data Compression #Network Packet Processing and Optimization #DNA and Biological Computing #Computer science #Focus (optics) #Relevance (law) #String searching algorithm #String (physics) #Matching (statistics) #Theoretical computer science #Current (fluid) #Edit distance #Data science #Machine learning #Artificial intelligence #Pattern matching #Information retrieval #Mathematics
- On the sorting-complexity of suffix tree construction
2000/11/01 by Martı́n Farach-Colton, Paolo Ferragina, S. Muthukrishnan · 3 citations
Computer Science · Biochemistry, Genetics and Molecular Biology · Mathematics · #Algorithms and Data Compression #Network Packet Processing and Optimization #DNA and Biological Computing #Generalized suffix tree #Suffix tree #Compressed suffix array #Time complexity #Suffix #String (physics) #Upper and lower bounds #Sorting #String searching algorithm #Combinatorics #Mathematics #Suffix array #Data structure #Algorithm #Computer science #Discrete mathematics
- A fast bit-vector algorithm for approximate string matching based on dynamic programming
1999/05/01 by Gene Myers · 43 citations
Computer Science · Mathematics · #Algorithm #Algorithms and Data Compression #Bit array #Computer science #Dynamic programming #Matching (statistics) #Mathematics #Natural Language Processing Techniques #Network Packet Processing and Optimization #Pattern matching #Set (abstract data type) #String (physics) #String searching algorithm #Subroutine #Substring
- Suffix arrays for multiple strings: A method for on-line multiple string searches
1996/01/01 by Fei Shi · 1 citation
Biochemistry, Genetics and Molecular Biology · Computer Science · Mathematics · #Algorithm #Algorithms and Data Compression #Approximate string matching #Artificial intelligence #Combinatorics #Compressed suffix array #Computer science #DNA and Biological Computing #Data structure #Discrete mathematics #Generalization #Generalized suffix tree #Mathematics #Network Packet Processing and Optimization #Pattern matching #String (physics) #String searching algorithm #Substring #Suffix #Suffix array #Suffix tree
- On-line construction of suffix trees
1995/09/01 by Esko Ukkonen, E. Ukkonen · 5 citations
Computer Science · Mathematics · #Algorithm #Algorithms and Data Compression #Combinatorics #Compressed suffix array #Computer science #Data structure #Discrete mathematics #Generalized suffix tree #Line (geometry) #Mathematics #Natural Language Processing Techniques #Network Packet Processing and Optimization #String (physics) #String searching algorithm #Suffix #Suffix array #Suffix tree #Symbol (formal) #Theory of computation #Time complexity
- Suffix Arrays: A New Method for On-Line String Searches
1993/10/01 by Udi Manber, Gene Myers · 108 citations
Biochemistry, Genetics and Molecular Biology · Computer Science · Mathematics · #Algorithm #Algorithms and Data Compression #Arithmetic #Combinatorics #Compressed suffix array #Computer science #DNA and Biological Computing #Data structure #Generalized suffix tree #Genomics and Phylogenetic Studies #Mathematics #String (physics) #String searching algorithm #Substring #Suffix #Suffix array #Suffix tree #Time complexity #sort
- Deterministic Sampling–A New Technique for Fast Pattern Matching
1991/02/01 by Uzi Vishkin · 6 citations
Computer Science · Mathematics · #Algorithm #Algorithms and Data Compression #Artificial intelligence #Computation #Computer science #Logarithm #Matching (statistics) #Mathematics #Network Packet Processing and Optimization #Parallel computing #Pattern matching #Preprocessor #Sample (material) #Sample size determination #Sampling (signal processing) #Speedup #Statistics #String (physics) #String searching algorithm #Time complexity #Tree traversal #semigroups and automata theory
- Generalized String Matching
1987/12/01 by Karl Abrahamson · 10 citations
Computer Science · Mathematics · #Algorithms and Data Compression #Approximate string matching #Artificial intelligence #Combinatorics #Commentz-Walter algorithm #Computer science #Discrete mathematics #Mathematics #Network Packet Processing and Optimization #Pattern matching #String (physics) #String metric #String searching algorithm #semigroups and automata theory
- A faster algorithm computing string edit distances
1980/02/01 by William Joseph Masek, William J. Masek, Michael S. Paterson · 5 citations
Computer Science · Mathematics · #Algorithm #Algorithms and Data Compression #Alphabet #Artificial intelligence #Combinatorics #Computer science #Discrete mathematics #Edit distance #Longest common subsequence problem #Mathematics #Natural Language Processing Techniques #Pattern matching #Programming language #Sequence (biology) #String (physics) #String searching algorithm #Subsequence #Symbol (formal) #semigroups and automata theory
- The Complexity of Pattern Matching for a Random String
1979/08/01 by Andrew Chi-Chih Yao · 2 citations
Biochemistry, Genetics and Molecular Biology · Computer Science · Mathematics · #Algorithms and Data Compression #Alphabet #Artificial intelligence #Combinatorics #Computer science #Conjecture #DNA and Biological Computing #Discrete mathematics #Matching (statistics) #Mathematical physics #Mathematics #Pattern matching #Statistics #String (physics) #String searching algorithm #semigroups and automata theory
- Fast Pattern Matching in Strings
1977/06/01 by Donald E. Knuth, James H. Morris, James H. Morris, Jr. +2 · 109 citations
Computer Science · Mathematics · #Algorithm #Algorithms and Data Compression #Artificial intelligence #Combinatorics #Computer science #Constant (computer programming) #Discrete mathematics #Matching (statistics) #Mathematics #Network Packet Processing and Optimization #Palindrome #Pattern matching #Set (abstract data type) #Statistics #String searching algorithm #Time complexity #semigroups and automata theory
- On the complexity of the Extended String-to-String Correction Problem
1975/01/01 by Robert A. Wagner · 1 citation
Computer Science · Mathematics · #Algorithms and Data Compression #Natural Language Processing Techniques #semigroups and automata theory #String (physics) #Swap (finance) #Sequence (biology) #Alphabet #Time complexity #Combinatorics #String searching algorithm #Computer science #Constant (computer programming) #Mathematics #Discrete mathematics #Algorithm #Pattern matching #Programming language
- The String-to-String Correction Problem
1974/01/01 by Robert A. Wagner, Michael J. Fischer · 18 citations
Computer Science · Mathematics · #Algorithm #Algorithms and Data Compression #Approximate string matching #Artificial intelligence #Bounded function #Combinatorics #Commentz-Walter algorithm #Computer science #Edit distance #Longest common subsequence problem #Longest increasing subsequence #Mathematics #Natural Language Processing Techniques #Pattern matching #Physics #Programming language #Software Testing and Debugging Techniques #String (physics) #String metric #String searching algorithm #Subsequence #Symbol (formal) #Theoretical physics
- Linear pattern matching algorithms
1973/10/01 by Peter Weiner · 19 citations
Computer Science · Mathematics · #Algorithms and Data Compression #Network Packet Processing and Optimization #Natural Language Processing Techniques #Algorithm #Matching (statistics) #Computer science #Pattern matching #String searching algorithm #Time complexity #Tree (set theory) #Theoretical computer science #Mathematics #Artificial intelligence #Combinatorics
- Rapid identification of repeated patterns in strings, trees and arrays
1972/01/01 by Richard M. Karp, Raymond E. Miller, Arnold L. Rosenberg · 1 citation
Computer Science · Mathematics · #Algorithms and Data Compression #Web Data Mining and Analysis #Graph Theory and Algorithms #Substring #Computer science #Pattern matching #Matching (statistics) #Identification (biology) #String searching algorithm #Tree (set theory) #Algorithm #Theoretical computer science #Approximate string matching #Mathematics #Artificial intelligence #Data structure #Combinatorics
- Monotonic run length text sampling and fake sampled positions
2026/07/23 by Simone Faro, Thierry Lecroq, Francesco Pio Marino +2
Computer Science · Decision Sciences · #Algorithms and Data Compression #Commentz-Walter algorithm #Context (archaeology) #Data Quality and Management #Matching (statistics) #Network Packet Processing and Optimization #Pattern matching #Sampling (signal processing) #String (physics) #String metric #String searching algorithm