Position Heaps for Parameterized Strings
Position Heaps for Parameterized Strings
复制标题
参数化字符串的位置堆
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
A. Shinohara
中科院分区：
文献类型：
--
作者：
Diptarama;Takashi Katsura;Y. Otomo;K. Narisawa;A. Shinohara
我们提出一种用于参数化字符串的新索引结构，称为参数化位置堆。参数化位置堆适用于参数化模式匹配问题，在该问题中，如果存在从模式的符号到子串的符号的双射映射，则模式与文本的一个子串匹配。我们提出一种文本的参数化位置堆的在线构建算法，并表明我们的算法相对于文本大小是线性时间运行的。我们还表明，通过使用参数化位置堆，我们能够相对于模式大小和字母表大小的乘积，在线性时间内找到模式在文本中的所有出现位置。
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.