The Parameterized Suffix Tray
The Parameterized Suffix Tray
复制标题
DOI：
10.1007/978-3-030-75242-2_18
复制
发表时间：
2020-12
期刊：
影响因子：
--
通讯作者：
Noriki Fujisato;Yuto Nakashima;Shunsuke Inenaga;H. Bannai;M. Takeda
中科院分区：
文献类型：
--
作者：
Noriki Fujisato;Yuto Nakashima;Shunsuke Inenaga;H. Bannai;M. Takeda
设$$\varSigma$$Σ和$$\varPI$$Π是不相交的字母表，分别称为静态字母表和参数字母表。如果在$$\varSigma$$Σ∪Π和$$上存在重命名二射，则称相同长度的两个字符串xandyover$$\varSigma\Σ\varPI$$匹配(p-Match\varPI$$Π，它是$$\varSigma$$Σ上的标识，并将x的字符映射到y的字符，以便两个字符串变得相同。在文本中找到给定模式的p匹配出现的问题的索引版本是字符串匹配中一个研究得很好的主题。在本文中，我们提出了一种最新的p匹配索引结构，称为输入文本T的参数化后缀托盘，表示为$$\mathsf{PSTray}(T)$$PSTray(T)。我们证明了$$\mathsf{PSTray}(T)$$PSTray(T)占用O(N)空间，并在$$O(m+\log(\sigma+\pi)+occ)中支持模式匹配查询O(m+Log(σ+π)+oc c)时间，其中是Oft的长度，Misse是查询模式P的长度，$$\pi$$π是$$|\varPI|$$|Π|INT的不同符号的数目，$$\sigma$$σ是$$|\varSigma|$$|Σ|inT和$$occ$$的不同符号数OCC是PINT的p匹配出现次数。我们还介绍了如何从参数化后缀树oft建立$$\mathsf{PSTray}(T)$$PSTray(T)Ino(N)time。
Let $$\varSigma $$ Σ and $$\varPi $$ Π be disjoint alphabets, respectively called the static alphabet and the parameterized alphabet. Two stringsxandyover $$\varSigma \cup \varPi $$ Σ ∪ Π of equal length are said toparameterized match(p-match) if there exists a renaming bijectionfon $$\varSigma $$ Σ and $$\varPi $$ Π which is identity on $$\varSigma $$ Σ and maps the characters ofxto those ofyso that the two strings become identical. The indexing version of the problem of finding p-matching occurrences of a given pattern in the text is a well-studied topic in string matching. In this paper, we present a state-of-the-art indexing structure for p-matching called theparameterized suffix trayof an input textT, denoted by $$\mathsf {PSTray}(T)$$ PSTray ( T ) . We show that $$\mathsf {PSTray}(T)$$ PSTray ( T ) occupiesO(n) space and supports pattern matching queries in $$O(m + \log (\sigma +\pi ) + occ )$$ O ( m + log ( σ + π ) + o c c ) time, wherenis the length oft,mis the length of a query patternP, $$\pi $$ π is the number of distinct symbols of $$|\varPi |$$ | Π | inT, $$\sigma $$ σ is the number of distinct symbols of $$|\varSigma |$$ | Σ | inTand $$ occ $$ occ is the number of p-matching occurrences ofPinT. We also present how to build $$\mathsf {PSTray}(T)$$ PSTray ( T ) inO(n) time from the parameterized suffix tree ofT.