Longest Common Abelian Factors and Large Alphabets
Longest Common Abelian Factors and Large Alphabets
复制标题
最长公共阿贝尔因子和大字母
DOI：
10.1007/978-3-319-46049-9_24
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Simon J. Puglisi and Shiho Sugimoto
中科院分区：
文献类型：
--
作者：
Golnaz Badkobeh;Travis Gagie;Szymon Grabowski;Yuto Nakashima;Simon J. Puglisi and Shiho Sugimoto
两个字符串X和Y被认为是阿贝尔相等的，如果X的字母可以被置换为Y（反之亦然）。最近，Alatabbi et al.（2015）考虑了最长的公共阿贝尔因子问题，我们被要求找到给定字符串对中存在的最长阿贝尔相等因子的长度。他们提供了一种使用时间和空间的算法，其中是字符串对的长度，是字母表的大小。在本文中，我们描述了一个算法，使用时间和空间，显着改善Alatabbi等人'。除非字母表很小。我们的算法利用了在分割、连接和相等测试下维护一组动态字符串的技术（Melhorn等人，Microbica 17（2），1997）。
Two stringsXandYare considered Abelian equal if the letters ofXcan be permuted to obtainY(and vice versa). Recently, Alatabbi et al. (2015) considered thelongest common Abelian factor problemin which we are asked to find the length of the longest Abelian-equal factor present in a given pair of strings. They provided an algorithm that usestime andspace, wherenis the length of the pair of strings andis the alphabet size. In this paper we describe an algorithm that usestime andspace, significantly improving Alatabbi et al.’s result unless the alphabet is small. Our algorithm makes use of techniques for maintaining a dynamic set of strings under split, join, and equality testing (Melhorn et al., Algorithmica 17(2), 1997).