
























Abelian string matching problems are becoming an object of considerable interest in last years. Very recently, Alatabbi et al. \cite{AILR2015} presented the first solution for the longest common Abelian factor problem for a pair of strings, reaching $O(σn^2)$ time with $O(σn \log 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.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。