Parameterized strings are a generalization of strings in that their characters are drawn from two different alphabets, where one is considered to be the alphabet of static characters and the other to be the alphabet of parameter characters. Two parameterized strings are a parameterized match if there is a bijection over all characters such that the bijection transforms one string to the other while keeping the static characters (i.e., it behaves as the identity on the static alphabet). Ganguly et al. [SODA 2017] proposed the parameterized Burrows--Wheeler transform (pBWT) as a variant of the Burrows--Wheeler transform for space-efficient parameterized pattern matching. In this paper, we propose an algorithm for computing the pBWT online by reading the characters of a given input string one-by-one from right to left. Our algorithm works in $O(|\Pi| \log n / \log \log n)$ amortized time for each input character, where $n$ and $\Pi$ denote the size of the input string and the alphabet of the parameter characters, respectively.
翻译：参数字符串是字符串的一般化, 其字符来自两种不同的字母, 其中一种被认为是静态字符的字母, 另一种被认为是参数字符的字母。 两个参数字符串是一个参数匹配, 如果对所有字符有一个双向线, 使双向将一个字符串转换到另一个字符串, 同时保留静态字符( 也就是说, 它作为静态字母上的身份) 。 Ganguly 等人 [SODA 2017] 提议将参数化的 Burrows- Wheeler 变换( pBWT) 作为 Burrows- Wheeler变换的变量, 用于空间高效参数模式匹配。 在本文中, 我们提出一个计算 pBWT 的算法, 通过从右到左读取给定的输入字符串的字符。 我们的算法在 $O ( ⁇ ⁇ ⁇ \ \ \ \ \ log n \ \ log\ \ \ log n ) 中工作, 每个输入字符串和 $\ p\ Pi$\ Pi 表示参数的字母的大小 。
相关内容
Alphabet is mostly a collection of companies. This newer Google is a bit slimmed down, with the companies that are pretty far afield of our main internet products contained in Alphabet instead.https://abc.xyz/
微信扫码咨询专知VIP会员