Construction of Aho Corasick automaton in linear time for integer alphabets

DOI10.1016/j.ipl.2005.11.019zbMath1178.68310OpenAlexW1991673591MaRDI QIDQ844159

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 arraysuffix tree

Mathematics Subject Classification ID

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

Related Items

All-pairs suffix/prefix in optimal time using Aho-Corasick space, Fast and Simple Computations Using Prefix Tables Under Hamming and Edit Distance, Accurate and Efficient Methods to Improve Multiple Circular Sequence Alignment, Reverse-Safe Text Indexing, Probabilistic Arithmetic Automata and Their Application to Pattern Matching Statistics, Fast circular dictionary-matching algorithm, Universal compressed text indexing, Searching and Indexing Circular Patterns, On suffix extensions in suffix trees

Cites Work

• Unnamed Item
• Unnamed Item
• Replacing suffix trees with enhanced suffix arrays
• On-line construction of suffix trees
• Suffix Arrays: A New Method for On-Line String Searches
• Linear-Time Construction of Suffix Arrays
• Space Efficient Linear Time Construction of Suffix Arrays
• Three Partition Refinement Algorithms
• Efficient string matching
• A Space-Economical Suffix Tree Construction Algorithm
• Fast Pattern Matching in Strings
• Algorithms on Strings, Trees and Sequences
• String Processing and Information Retrieval