A fast string searching algorithm
From MaRDI portal
Publication:3090391
DOI10.1145/359842.359859zbMath1219.68165OpenAlexW2134826720WikidataQ55879864 ScholiaQ55879864MaRDI QIDQ3090391
J. Strother Moore, Robert S. Boyer
Publication date: 31 August 2011
Published in: Communications of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/359842.359859
Related Items
Approximate string matching using compressed suffix arrays, Structural properties of the string statistics problem, Efficient string matching with k mismatches, An optimal algorithm to compute all the covers of a string, Single character searching methods and the shift-or pattern-matching algorithm, Dynamic dictionary matching with failure functions, Tight bounds on the complexity of the Apostolico-Giancarlo algorithm, Document retrieval with one wildcard, Speeding up two string-matching algorithms, On Boyer-Moore automata, A sublinear algorithm for approximate keyword searching, Dynamic dictionary matching, Automata evaluation and text search protocols with simulation-based security, Efficient special cases of pattern matching with swaps, Scaled and permuted string matching, Resource scheduling with variable requirements over time, Permuted scaled matching, Light-based string matching, Accelerating Boyer-Moore searches on binary texts, On two-dimensional pattern-matching languages and their decision problems, On obtaining the Boyer-Moore string-matching algorithm by partial evaluation, Efficient parameterized string matching, Pattern matching with don't cares and few errors, Efficient matching of nonrectangular shapes., Data structures and algorithms for approximate string matching, Remarks on string-matching and one-way multihead automata, Fast string matching with k differences, Saving comparisons in the Crochemore-Perrin string-matching algorithm, Matching patterns in strings subject to multi-linear transformations, La reconnaissance des facteurs d'un langage fini dans un texte en temps linéaire. (Recognition of the factors of a finite language in a text in linear time), String-matching with OBDDs, A unifying look at the Apostolico--Giancarlo string-matching algorithm, Some string matching problems from bioinformatics which still need better solutions, Unification theory, Practical and flexible pattern matching over Ziv-Lempel compressed text., String matching and 1d lattice gases, A filtering algorithm for \(k\)-mismatch with don't cares, A fast algorithm for the all-pairs suffix-prefix problem, A new filtration method and a hybrid strategy for approximate string matching, A string searching algorithm, Efficient index for retrieving top-\(k\) most frequent documents, Improved and self-tuned occurrence heuristics, A filtration method for order-preserving matching, A new efficient indexing algorithm for one-dimensional real scaled patterns, A compact representation of nondeterministic (suffix) automata for the bit-parallel approach, Fast string searching by finding subkeys in subtext, String overlaps, pattern matching, and nontransitive games, Periods in strings, Average complexity of backward \(q\)-gram string matching algorithms, An analysis of the Karp-Rabin string matching algorithm, A fast pattern matching algorithm derived by transformational and assertional reasoning, Worst-case behavior of string-searching algorithms, Dictionary matching with a bounded gap in pattern or in text, Worst-case efficient single and multiple string matching on packed texts in the word-RAM model, Verifying and enumerating parameterized border arrays, Searching for a set of correlated patterns, A simple fast hybrid pattern-matching algorithm, A fast algorithm for order-preserving pattern matching, Property matching and weighted matching, Usefulness of the Karp-Miller-Rosenberg algorithm in parallel computations on strings and arrays, Correctness and efficiency of pattern matching algorithms, String matching with lookahead, How the character comparison order shapes the shift function of on-line pattern matching algorithms, A fast algorithm for string matching with mismatches, String-matching on ordered alphabets, A variation on the Boyer-Moore algorithm, Fast average-case pattern matching by multiplexing sparse tables, Designing optimal- and fast-on-average pattern matching algorithms, Quantum pattern matching fast on average, Fast pattern-matching on indeterminate strings, Tight comparison bounds for the string prefix-matching problem, Faster string matching based on hashing and bit-parallelism, Fast searching in packed strings, Identifying periodic occurrences of a template with applications to protein structure, Fast two-dimensional pattern matching, Two-dimensional dictionary matching, An aggressive algorithm for multiple string matching, A new taxonomy of sublinear right-to-left scanning keyword pattern matching algorithms, La reconnaissance des facteurs d'un mot dans un texte, Simple and efficient string matching with k mismatches, Improving practical exact string matching, An improved algorithm to check for polygon similarity, On the size of Boyer-Moore automata, Faster pattern matching with character classes using prime number encoding, On polygon similarity, Computationally secure pattern matching in the presence of malicious adversaries, Shift-or string matching with super-alphabets, Disjunctive partial deduction of a right-to-left string-matching algorithm, Fast parameterized matching with \(q\)-grams, Optimal parallel two dimensional text searching on a CREW PRAM, Real two dimensional scaled matching, The factors analysis and algorithm implementation of single-pattern matching, Average-optimal string matching, Two-dimensional pattern matching by two-dimensional on-line tessellation acceptors, The smallest automaton recognizing the subwords of a text, Essence of generalized partial computation, Three one-way heads cannot do string matching, Alphabet dependence in parameterized matching, String matching over compressed text on handheld devices using tagged sub-optimal code (TSC), A complete mechanization of correctness of a string-preprocessing algorithm, Inferring strings from position heaps in linear time, An adaptive memory matheuristic for the set orienteering problem, Ranking and unranking bordered and unbordered words, String Covering: A Survey, Quantum algorithms for learning hidden strings with applications to matroid problems, THEORETICAL ISSUES OF SEARCHING AERIAL PHOTOGRAPHS: A BIRD'S EYE VIEW, Program transformation system based on generalized partial computation, Efficient protocols for set intersection and pattern matching with security against malicious and covert adversaries, Parallel String Matching, A new regular grammar pattern matching algorithm., Shimba-an environment for reverse engineering Java software systems, A Heuristic For Computing Repeats With A Factor Oracle: Application To Biological Sequences, New and faster filters for multiple approximate string matching, PAMA: A FAST STRING MATCHING ALGORITHM, State Complexity of Neighbourhoods and Approximate Pattern Matching, The Range Automaton: an efficient approach to text-searching, Fast algorithms for two dimensional and multiple pattern matching, Boyer-Moore approach to approximate string matching, ADAPTING BOYER-MOORE-LIKE ALGORITHMS FOR SEARCHING HUFFMAN ENCODED TEXTS, ALGORITHMS FOR JUMBLED PATTERN MATCHING IN STRINGS, An aperiodicity problem for multiwords, On-Line Approximate String Searching Algorithms: Survey and Experimental Results, An 0(1) time algorithm for string matching, Multiple filtration and approximate pattern matching, A subquadratic algorithm for approximate limited expression matching, A concurrent multi-string matching from multi-text algorithm based on the algorithm of Hamiltonian Path Problem and DNA computation, A Bit-Parallel Exact String Matching Algorithm for Small Alphabet, Weighted approximate parameterized string matching, Succinct Non-overlapping Indexing, Dictionary Matching with Uneven Gaps, Pattern matching in hypertext, A weak approach to suffix automata simulation for exact and approximate string matching, Accelerating Boyer Moore Searches on Binary Texts, On String Matching in Chunked Texts, On the relationship between histogram indexing and block-mass indexing, Improved characters distance sampling for online and offline text searching, State Complexity of Neighbourhoods and Approximate Pattern Matching, Efficient online string matching based on characters distance text sampling, Order-preserving matching, Towards optimal packed string matching, Approximating the maximum consecutive subsums of a sequence, Approximate Boyer-Moore string matching for small alphabets, Fast algorithms for single and multiple pattern Cartesian tree matching, On-line string matching algorithms: survey and experimental results, Partial words and the critical factorization theorem revisited, Efficient one-dimensional real scaled matching, Worst Case Efficient Single and Multiple String Matching in the RAM Model, An algorithm to compute the character access count distribution for pattern matching algorithms, A faster quick search algorithm, Parallel String Matching Algorithms, String-Matching and Alignment Algorithms for Finding Motifs in NGS Data, IDPM: An Improved Degenerate Pattern Matching Algorithm for Biological Sequences, On-line weighted pattern matching, Prefix-free regular languages and pattern matching, Generalized function matching, On the string matching with \(k\) mismatches, AN IMPROVED PREFIX-FREE REGULAR-EXPRESSION MATCHING, Fast string matching for multiple searches, A high-speed dynamic full-text search method by using memory management, A randomized numerical aligner (rNA), Permuted pattern matching algorithms on multi-track strings, The wide window string matching algorithm, Partial words and the critical factorization theorem, Boosting Pattern Matching Performance via k-bit Filtering, A parameterized multilevel pattern matching architecture on FPGAs for network intrusion detection and prevention, Unnamed Item, NR‐grep: a fast and flexible pattern‐matching tool, Fast String Matching in Stationary Ergodic Sources, Fast string matching by using probabilities: on an optimal mismatch variant of Horspool's algorithm, Fast parallel and serial multidimensional approximate array matching, Improved pattern-scan-order algorithms for string matching, Milestones from the Pure Lisp Theorem Prover to ACL2, Efficient Protocols for Set Intersection and Pattern Matching with Security Against Malicious and Covert Adversaries, Succinct non-overlapping indexing, Watson-Crick Conjugate and Commutative Words, Unnamed Item, Creating improvisations on chord progressions using suffix trees, Self-overlapping Occurrences and Knuth-Morris-Pratt Algorithm for Weighted Matching, Finite Automata for Generalized Approach to Backward Pattern Matching, Regular Expressions at Their Best: A Case for Rational Design, Unnamed Item, The order-preserving pattern matching problem in practice, A brief history of parameterized matching problems, Fast string matching for DNA sequences, A New String Matching Algorithm, Testing Stream Ciphers by Finding the Longest Substring of a Given Density, Fast Searching in Packed Strings, An improvement of the Aho-Corasick machine, Transducers and repetitions, The conjugacy problem in subgroups of right-angled Artin groups, Efficient Algorithms for the Order Preserving Pattern Matching Problem, Speeding up two string-matching algorithms, Two-pattern strings. I: A recognition algorithm, Unnamed Item, EFFICIENT VARIANTS OF THE BACKWARD-ORACLE-MATCHING ALGORITHM, AN ADAPTIVE HYBRID PATTERN-MATCHING ALGORITHM ON INDETERMINATE STRINGS, Performance Estimation Using Symbolic Data, Time-space-optimal string matching, INFERRING STRINGS FROM COVER ARRAYS, Sliding suffix tree, Bit-parallel (\(\delta ,\gamma\))-matching and suffix automata, A SPACE EFFICIENT BIT-PARALLEL ALGORITHM FOR THE MULTIPLE STRING MATCHING PROBLEM, FLEXIBLE MUSIC RETRIEVAL IN SUBLINEAR TIME, Correctness of substring-preprocessing in Boyer-Moore's pattern matching algorithm, Conjugacy in Artin groups of extra-large type., Fast Order-Preserving Pattern Matching, Order-preserving pattern matching indeterminate strings, Quantum algorithm for learning secret strings and its experimental demonstration, Application of max-plus algebra to biological sequence comparisons
