Efficient string matching
From MaRDI portal
Publication:4055184
DOI10.1145/360825.360855zbMath0301.68048OpenAlexW2099964107WikidataQ55870932 ScholiaQ55870932MaRDI QIDQ4055184
A. V. Aho, Margaret J. Corasick
Publication date: 1975
Published in: Communications of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/360825.360855
Related Items (only showing first 100 items - show all)
A new regular grammar pattern matching algorithm. ⋮ Dynamic dictionary matching with failure functions ⋮ Sublinear approximate string matching and biological applications ⋮ Pattern matching in a digitized image ⋮ Dynamic dictionary matching ⋮ Automata and forbidden words ⋮ Average complexity of exact and approximate multiple string matching ⋮ A fast algorithm for the unique decipherability of multivalued encodings ⋮ Compression of finite-state automata through failure transitions ⋮ Construction of Aho Corasick automaton in linear time for integer alphabets ⋮ Efficient parameterized string matching ⋮ A general compression algorithm that supports fast searching ⋮ On-line construction of suffix trees ⋮ Efficient matching of nonrectangular shapes. ⋮ On the look-ahead problem in lexical analysis ⋮ A subquadratic algorithm for approximate limited expression matching ⋮ Giant complete automaton for uncertain multiple string matching and its high speed construction algorithm ⋮ 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) ⋮ The submatrices character count problem: An efficient solution using separable values ⋮ From searching text to querying XML streams ⋮ On the complexity of deciding avoidability of sets of partial words ⋮ A fast algorithm for the all-pairs suffix-prefix problem ⋮ A polynomial algorithm testing partial confluence of basic semi-Thue systems ⋮ Inventories of unavoidable languages and the word-extension conjecture ⋮ On updating suffix tree labels ⋮ Analysis of two-dimensional approximate pattern matching algorithms ⋮ Sparse approaches for the exact distribution of patterns in long state sequences generated by a Markov source ⋮ Efficient seed computation revisited ⋮ A survey on tree matching and XML retrieval ⋮ A string searching algorithm ⋮ A graph-theoretic model to solve the approximate string matching problem allowing for translocations ⋮ Motif matching using gapped patterns ⋮ On the bit-parallel simulation of the nondeterministic Aho-Corasick and suffix automata for a set of patterns ⋮ BLIM: A new bit-parallel pattern matching algorithm overcoming computer word size limitation ⋮ Optimizing restriction site placement for synthetic genomes ⋮ Fast string searching by finding subkeys in subtext ⋮ A linear-time algorithm for finding approximate shortest common superstrings ⋮ Parameterized longest previous factor ⋮ String matching with variable length gaps ⋮ Dictionary matching with a bounded gap in pattern or in text ⋮ Number of holes in unavoidable sets of partial words. II. ⋮ 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 ⋮ Asynchronous trace-matching automata ⋮ Universal compressed text indexing ⋮ Fast profile matching algorithms - A survey ⋮ Usefulness of the Karp-Miller-Rosenberg algorithm in parallel computations on strings and arrays ⋮ Multiple pattern matching: a Markov chain approach ⋮ Efficient polynomial-time algorithms for the constrained LCS problem with strings exclusion ⋮ On string matching with mismatches ⋮ On-line weighted pattern matching ⋮ Multiple matching of parameterized patterns ⋮ On the string matching with \(k\) mismatches ⋮ A string-matching interpretation of the equation \(x^ m y^ n = z^ p\) ⋮ Fast average-case pattern matching by multiplexing sparse tables ⋮ A space-efficient alphabet-independent Four-Russians' lookup table and a multithreaded Four-Russians' edit distance algorithm ⋮ A practical method for implementing string pattern matching machines ⋮ 2D Lyndon words and applications ⋮ A grouping approach for succinct dynamic dictionary matching ⋮ A sheaf-theoretic approach to pattern matching and related problems ⋮ On the complexity of learning strings and sequences ⋮ Approximate string matching with suffix automata ⋮ Fast searching in packed strings ⋮ Permuted pattern matching algorithms on multi-track strings ⋮ On finding common subtrees ⋮ Fast two-dimensional pattern matching ⋮ Two-dimensional dictionary matching ⋮ An index-split Bloom filter for deep packet inspection ⋮ 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 ⋮ Genome wide study of NF-Y type CCAAT boxes in unidirectional and bidirectional promoters in human and mouse ⋮ Thread allocation in CMP-based multithreaded network processors ⋮ A faster algorithm for matching a set of patterns with variable length don't cares ⋮ Internal dictionary matching ⋮ Unavoidable sets of partial words ⋮ Testing avoidability on sets of partial words is hard ⋮ Efficient pattern matching in elastic-degenerate strings ⋮ The shortest path problem with forbidden paths ⋮ Optimal parallel two dimensional text searching on a CREW PRAM ⋮ An improvement of the Aho-Corasick machine ⋮ Transducers and repetitions ⋮ Dynamic dictionary matching in external memory ⋮ Integrating code generation and peephole optimization ⋮ Fast pattern matching in indexed texts ⋮ An efficient null-free procedure for deciding regular language membership ⋮ Distributions of pattern statistics in sparse Markov models ⋮ On computing all suboptimal alignments ⋮ Average-optimal string matching ⋮ Fast and practical approximate string matching ⋮ Two-dimensional pattern matching by two-dimensional on-line tessellation acceptors ⋮ An \(O(| T| ^ 3)\) algorithm for testing the Church-Rosser property of Thue systems ⋮ Tree pattern matching with a more general notion of occurrence of the pattern. ⋮ Cut and paste ⋮ Reducing space for index implementation. ⋮ The smallest automaton recognizing the subwords of a text ⋮ Alphabet dependence in parameterized matching ⋮ A comparative study of dictionary matching with gaps: limitations, techniques and challenges ⋮ On the complexity of recognizing Wheeler graphs
This page was built for publication: Efficient string matching
