Construction of Aho Corasick automaton in linear time for integer alphabets

DOI10.1016/J.IPL.2005.11.019MaRDI QIDQ844159zbMATH OpenOpenAlexFDO

Authors Shiri Dori, Gad M. Landau

Publication date 18 January 2010

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ipl.2005.11.019

zbMATH Keywords

design of algorithmsstring matchingsuffix treesuffix array

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Nonnumerical algorithms (68W05)

Recommendations

• Combinatorial Pattern Matching
• An efficient linear pseudo-minimization algorithm for Aho-Corasick automata
• scientific article; zbMATH DE number 1538036
• scientific article; zbMATH DE number 3982522
• Constructions for alternating finite automata^∗
• EFFICIENT AUTOMATA CONSTRUCTIONS AND APPROXIMATE AUTOMATA
• Building the minimal automaton of \(A ^{*} X\) in linear time, when \(X\) is of bounded cardinality
• On the bit-parallel simulation of the nondeterministic Aho-Corasick and suffix automata for a set of patterns
• Minimisation of acyclic deterministic automata in linear time
• scientific article; zbMATH DE number 1941938

Cites work

• scientific article; zbMATH DE number 3913713 (Why is no real title available?)
• scientific article; zbMATH DE number 2038766 (Why is no real title available?)
• A Space-Economical Suffix Tree Construction Algorithm
• Algorithms on Strings, Trees and Sequences
• Efficient string matching
• Fast Pattern Matching in Strings
• Linear-time construction of suffix arrays (extended abstract)
• On-line construction of suffix trees
• Replacing suffix trees with enhanced suffix arrays
• Space efficient linear time construction of suffix arrays
• String Processing and Information Retrieval
• Suffix Arrays: A New Method for On-Line String Searches
• Three Partition Refinement Algorithms

Cited in

(12)

• A Table Compression Method for Extended Aho-Corasick Automaton
• Combinatorial Pattern Matching
• Universal compressed text indexing
• Probabilistic Arithmetic Automata and Their Application to Pattern Matching Statistics
• Accurate and efficient methods to improve multiple circular sequence alignment
• All-pairs suffix/prefix in optimal time using Aho-Corasick space
• Fast and simple computations using prefix tables under Hamming and edit distance
• Searching and indexing circular patterns
• Fast circular dictionary-matching algorithm
• On suffix extensions in suffix trees
• An efficient linear pseudo-minimization algorithm for Aho-Corasick automata
• Reverse-safe text indexing

This page was built for publication: Construction of Aho Corasick automaton in linear time for integer alphabets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q844159)