A note on the longest common Abelian factor problem

Original · EN

Abelian string matching problems are becoming an object of considerable interest in last years. Very recently, Alatabbi et al. AILR2015 presented the first solution for the longest common Abelian factor problem for a pair of strings, reaching O(σn²) time with O(σn n) bits of space, where n is the length of the strings and σ is the alphabet size. In this note we show how the time complexity can be preserved while the space is reduced by a factor of σ, and then how the time complexity can be improved, if the alphabet is not too small, when superlinear space is allowed.