In this paper we consider the problem of computing the longest common abelian factor (LCAF) between two given strings. We present a simple O(?n2)O(?n2) 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.
Algorithms for Longest Common Abelian Factors
Langiu Alessio;
2016
Abstract
In this paper we consider the problem of computing the longest common abelian factor (LCAF) between two given strings. We present a simple O(?n2)O(?n2) 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.File in questo prodotto:
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
