Two strings X and Y are considered Abelian equal if the letters of X can be permuted to obtain Y (and vice versa). Recently, Alatabbi et al. (2015) considered the longest common Abelian factor problem in 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 uses O(σn~2) time and O(σn) space, where n is the length of the pair of strings and a is the alphabet size. In this paper we describe an algorithm that uses O(n~2 log~2 n log~* n) time and O(n log~2 n) space, 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., Algorith-mica 17(2), 1997).
展开▼
机译：如果可以置换X的字母以获得Y（反之亦然），则将两个字符串X和Y视为阿贝尔等于。最近，Alatabbi等人。 （2015年）考虑了最长的公共阿贝尔因子问题，要求我们找出给定的弦对中存在的最长阿贝尔相等因子的长度。他们提供了一种使用O（σn〜2）时间和O（σn）空间的算法，其中n是字符串对的长度，而a是字母的大小。在本文中，我们描述了一种使用O（n〜2 log〜2 n log〜* n）时间和O（n log〜2 n）空间的算法，除非字母表很小，否则将显着改善Alatabbi等人的结果。我们的算法利用了在拆分，连接和相等性测试下维护动态字符串集的技术（Melhorn等，Algorith-mica 17（2），1997）。
展开▼
