1. Algorithms for Longest Common Abelian Factors.
- Author
-
Alatabbi, Ali, Iliopoulos, Costas S., Langiu, Alessio, and Rahman, M. Sohel
- Subjects
ABELIAN groups ,ALGORITHMS ,LINEAR systems ,STRING theory ,QUADRATIC equations - Abstract
In this paper we consider the problem of computing the longest common abelian factor (LCAF) between two given strings. We present a simple time algorithm, where n is the length of the strings and 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. [ABSTRACT FROM AUTHOR]
- Published
- 2016
- Full Text
- View/download PDF