Algorithms for longest common abelian factors

DOI10.1142/S0129054116500143MaRDI QIDQ2833540zbMATH OpenOpenAlexFDO

Authors Ali Alatabbi, Costas S. Iliopoulos, Alessio Langiu, M. Sohel Rahman

Publication date 18 November 2016

Published in International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1503.00049

zbMATH Keywords

abelian matchabelian propertiesalgorithmlinearlongest common factorParikh vector

Mathematics Subject Classification ID

Combinatorics on words (68R15) Algorithms on strings (68W32)

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(sigma{n}^2)$ time algorithm, where $n$ is the length of the strings and $sigma$ 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.

Recommendations

• Longest common abelian factors and large alphabets
• Regular abelian periods and longest common abelian factors on run-length encoded strings
• On Abelian Longest Common Factor with and without RLE
• Subquadratic-time algorithms for abelian stringology problems
• scientific article; zbMATH DE number 4007744

Cites work

• Indexing permutations for binary strings
• On Context-Free Languages
• Sub-quadratic time and linear space data structures for permutation matching in binary strings

Cited in

(8)

• Computing abelian string regularities based on RLE
• Computing the longest previous factor
• Longest common abelian factors and large alphabets
• scientific article; zbMATH DE number 4007744 (Why is no real title available?)
• On Abelian Longest Common Factor with and without RLE
• Quasi-Linear-Time Algorithm for Longest Common Circular Factor
• Regular abelian periods and longest common abelian factors on run-length encoded strings
• Longest property-preserved common factor

This page was built for publication: Algorithms for longest common abelian factors

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2833540)