Direct linear time construction of parameterized suffix and LCP arrays for constant alphabets

DOI10.1007/978-3-030-32686-9_27MaRDI QIDQ6536267zbMATH OpenFDO

Authors Noriki Fujisato, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda

Publication date 19 April 2024

Full work available at URL https://doi.org/10.1007/978-3-030-32686-9_27

zbMATH Keywords

parameterized pattern matchingparameterized suffix array paramterized LCP array

Mathematics Subject Classification ID

Algorithms on strings (68W32)

Recommendations

• Lightweight parameterized suffix array construction
• Towards a real time algorithm for parameterized longest common prefix computation
• Parameterized longest previous factor
• Linear-time construction of suffix arrays (extended abstract)
• p-suffix sorting as arithmetic coding

Cites work

• p-suffix sorting as arithmetic coding
• Computing longest previous factor in linear time and applications
• Constructing suffix arrays in linear time
• Generalization of a suffix tree for RNA structural pattern matching
• scientific article; zbMATH DE number 1306895 (Why is no real title available?)
• scientific article; zbMATH DE number 1786458 (Why is no real title available?)
• Lightweight parameterized suffix array construction
• Linear work suffix array construction
• Parameterized Duplication in Strings: Algorithms and an Application to Software Maintenance
• Parameterized pattern matching: Algorithms and applications
• pBWT: achieving succinct data structures for parameterized pattern matching and related problems
• Position heaps for parameterized strings
• Position heaps: a simple and dynamic text indexing data structure
• Space efficient linear time construction of suffix arrays
• Theoretical and Practical Improvements on the RMQ-Problem, with Applications to LCA and LCE
• Variations of the parameterized longest previous factor

Cited in

(3)

• Reconstructing parameterized strings from parameterized suffix and LCP arrays
• Breaking a barrier in constructing compact indexes for parameterized pattern matching
• Inverting parameterized Burrows-Wheeler transform

This page was built for publication: Direct linear time construction of parameterized suffix and LCP arrays for constant alphabets

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