A compact representation of nondeterministic (suffix) automata for the bit-parallel approach

DOI10.1016/j.ic.2011.03.006zbMath1279.68137OpenAlexW2037649997MaRDI QIDQ418159

Simone Faro, Emanuele Giaquinta, Domenico Cantone

Publication date: 24 May 2012

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2011.03.006

zbMATH Keywords

stringsbit-parallelismBNDMfactorization of stringsnondeterministic automatonnondeterministic suffix automatonShift-And

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Algorithms on strings (68W32)

Related Items

The Range Automaton: an efficient approach to text-searching ⋮ Run-Length Encoded Nondeterministic KMP and Suffix Automata ⋮ A weak approach to suffix automata simulation for exact and approximate string matching ⋮ Fast and flexible packed string matching ⋮ Compact suffix automata representations for searching long patterns ⋮ On a compact encoding of the swap automaton ⋮ Linear and Efficient String Matching Algorithms Based on Weak Factor Recognition ⋮ A Very Fast String Matching Algorithm Based on Condensed Alphabets ⋮ Efficient string matching based on a two-step simulation of the suffix automaton

Cites Work

• Unnamed Item
• Shift-or string matching with super-alphabets
• A fast string searching algorithm
• Multipattern string matching with q -grams
• Efficient randomized pattern-matching algorithms
• Fast Pattern Matching in Strings
• Fast and flexible string matching by combining bit-parallelism and suffix automata
• String Processing and Information Retrieval