Algorithms for Longest Common Abelian Factors

作者：Alatabbi Ali^*; Iliopoulos Costas S; Langiu Alessio; Rahman M Sohel

来源：International Journal of Foundations of Computer Science, 2016, 27(5): 529-543.

DOI：10.1142/S0129054116500143

• Longest common factor
• linear
• algorithm
• abelian properties
• abelian match
• Parikh vector

In this paper(a) we consider the problem of computing the longest common abelian factor (LCAF) between two given strings. We present a simple O (sigma n(2)) time algorithm, where n is the length of the strings and sigma is the alphabet size, and a sub-quadratic running time solution for the binary string case, both having linear space requirement. Furthermore, we present a modified algorithm applying some interesting tricks and experimentally show that the resulting algorithm runs faster.

• 出版日期2016-8