Position heaps for parameterized strings

DOI10.4230/LIPICS.CPM.2017.8MaRDI QIDQ5110872zbMATH OpenOpenAlexFDO

Authors Diptarama, Takashi Katsura, Yuhei Otomo, Kazuyuki Narisawa, Ayumi Shinohara

Publication date 25 May 2020

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

zbMATH Keywords

indexing structureparameterized pattern matchingposition heapstring matching

Mathematics Subject Classification ID

Data structures (68P05) Online algorithms; streaming algorithms (68W27) Algorithms on strings (68W32)

Abstract: We propose a new indexing structure for parameterized strings, called parameterized position heap. Parameterized position heap is applicable for parameterized pattern matching problem, where the pattern matches a substring of the text if there exists a bijective mapping from the symbols of the pattern to the symbols of the substring. We propose an online construction algorithm of parameterized position heap of a text and show that our algorithm runs in linear time with respect to the text size. We also show that by using parameterized position heap, we can find all occurrences of a pattern in the text in linear time with respect to the product of the pattern size and the alphabet size.

Recommendations

• On-line construction of position heaps
• Simpler FM-index for parameterized string matching
• Position heaps: a simple and dynamic text indexing data structure
• A framework for dynamic parameterized dictionary matching
• Efficient parameterized string matching

Cited in

(8)

• The parameterized position heap of a trie
• Parameterized DAWGs: efficient constructions and bidirectional pattern searches
• On-line construction of position heaps
• New algorithms for position heaps
• Computing the parameterized Burrows-Wheeler transform online
• Direct linear time construction of parameterized suffix and LCP arrays for constant alphabets
• Efficient parameterized pattern matching in sublinear space
• Breaking a barrier in constructing compact indexes for parameterized pattern matching

This page was built for publication: Position heaps for parameterized strings

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