A fast string searching algorithm
From MaRDI portal
Publication:3090391
DOI10.1145/359842.359859zbMath1219.68165DBLPjournals/cacm/BoyerM77OpenAlexW2134826720WikidataQ55879864 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 (only showing first 100 items - show all)
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
This page was built for publication: A fast string searching algorithm
