Parameterized DAWGs: efficient constructions and bidirectional pattern searches

DOI10.1016/j.tcs.2022.09.008MaRDI QIDQ2676460

Ryo Yoshinaka, Yuto Nakashima, Hideo Bannai, Noriki Fujisato, Diptarama Hendrian, Ayumi Shinohara, Katsuhito Nakashima, Masayuki Takeda, Shunsuke Inenaga

Publication date: 27 September 2022

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2002.06786

zbMATH Keywords

suffix trees; parameterized matching; suffix automata; DAWGs

Mathematics Subject Classification ID

68Qxx: Theory of computing

Cites Work

• Unnamed Item
• The smallest automaton recognizing the subwords of a text
• Transducers and repetitions
• Generalization of a suffix tree for RNA structural pattern matching
• Parameterized pattern matching: Algorithms and applications
• \(p\)-suffix sorting as arithmetic coding
• On-line construction of parameterized suffix trees for large alphabets
• Simpler FM-index for parameterized string matching
• The parameterized position heap of a trie
• A brief history of parameterized matching problems
• Lightweight Parameterized Suffix Array Construction
• pBWT: Achieving Succinct Data Structures for Parameterized Pattern Matching and Related Problems
• Position Heaps for Parameterized Strings
• A theory of parameterized pattern matching
• DAWGs for Parameterized Matching: Online Construction and Related Indexing Structures