Computing Abelian String Regularities Based on RLE
Computing Abelian String Regularities Based on RLE
复制标题
基于RLE计算阿贝尔弦正则
DOI：
10.1007/978-3-319-78825-8_34
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Masayuki Takeda
中科院分区：
文献类型：
--
作者：
Shiho Sugimoto;Naoki Noda;Shunsuke Inenaga;Hideo Bannai;Masayuki Takeda
如果 x 是 y 的排列，则两个字符串 x 和 y 被称为阿贝尔等价，反之亦然。如果字符串 z 满足 xandy 为阿贝尔等价，则 z 被称为阿贝尔平方。如果一个字符串 w 可以分解为字符串序列，使得 ... 都是阿贝尔等价的，并且是 的排列的子串，那么我们就说它具有规则的阿贝尔周期 (p,t)，其中。如果一个字符串的子串和另一个字符串的子串是阿贝尔等价的，那么这两个子串就被称为and的公共阿贝尔因子，如果长度是and的最大公共阿贝尔因子，那么这两个子串就被称为and的最长公共阿贝尔因子。我们提出了使用字符串的游程长度编码（RLE）来计算这些阿贝尔正则的有效算法。对于给定的长度为 n 且 RLE 大小为 m 的字符串，我们提出了计算在 winO(mn) 时间内出现的所有阿贝尔平方以及在 winO(mn) 时间内发生的所有规则阿贝尔周期的算法。对于两个给定的字符串andof总长度nand总RLE大小m，我们提出了一种及时计算所有最长公共阿贝尔因子的算法。
Two stringsxandyare said to be Abelian equivalent ifxis a permutation ofy, or vice versa. If a stringzsatisfieswithxandybeing Abelian equivalent, thenzis said to be anAbelian square. If a stringwcan be factorized into a sequenceof strings such that, ...,are all Abelian equivalent andis a substring of a permutation of, thenwis said to have aregular Abelian period(p,t) whereand. If a substringof a stringand a substringof another stringare Abelian equivalent, then the substrings are said to be a common Abelian factor ofandand if the lengthis the maximum of such then the substrings are said to be alongest common Abelian factorofand. We propose efficient algorithms which compute these Abelian regularities using therun length encoding (RLE)of strings. For a given stringwof lengthnwhose RLE is of sizem, we propose algorithms which compute all Abelian squares occurring inwinO(mn) time, and all regular Abelian periods ofwinO(mn) time. For two given stringsandof total lengthnand of total RLE sizem, we propose an algorithm which computes all longest common Abelian factors intime.