Search

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]

A fundamental problem in music is to classify songs according to their rhythm. A rhythm is represented by a sequence of “Quick” (Q) and “Slow” (S) symbols, which correspond to the (relative) duration of notes, such that S = 2Q. In this paper, we present an efficient algorithm for locating the maximum-length substring of a music text t that can be covered by a given rhythm r. [ABSTRACT FROM AUTHOR]