Algorithms for Longest Common Abelian Factors

Ali Alatabbi; Costas S. Iliopoulos; Alessio Langiu; M. Sohel Rahman

doi:10.1142/S0129054116500143

Algorithms for Longest Common Abelian Factors

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

Informatics

Research output: Contribution to journal › Article › peer-review

2 Citations (Scopus)

Abstract

In this paper we consider the problem of computing the longest common abelian factor (LCAF) between two given strings. We present a simple (σ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.

Original language	English
Pages (from-to)	529-543
Number of pages	15
Journal	INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE
Volume	27
Issue number	5
DOIs	https://doi.org/10.1142/S0129054116500143
Publication status	Published - Aug 2016

Access to Document

10.1142/S0129054116500143

http://arxiv.org/abs/1503.00049

Cite this

@article{8522f3e664af4aabb4be3a8c6daf5d0a,

title = "Algorithms for Longest Common Abelian Factors",

abstract = "In this paper we consider the problem of computing the longest common abelian factor (LCAF) between two given strings. We present a simple (σ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.",

author = "Ali Alatabbi and Iliopoulos, {Costas S.} and Alessio Langiu and Rahman, {M. Sohel}",

year = "2016",

month = aug,

doi = "10.1142/S0129054116500143",

language = "English",

volume = "27",

pages = "529--543",

journal = "INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE",

issn = "0129-0541",

publisher = "World Scientific Publishing Co. Pte Ltd",

number = "5",

}

TY - JOUR

T1 - Algorithms for Longest Common Abelian Factors

AU - Alatabbi, Ali

AU - Iliopoulos, Costas S.

AU - Langiu, Alessio

AU - Rahman, M. Sohel

PY - 2016/8

Y1 - 2016/8

N2 - In this paper we consider the problem of computing the longest common abelian factor (LCAF) between two given strings. We present a simple (σ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.

AB - In this paper we consider the problem of computing the longest common abelian factor (LCAF) between two given strings. We present a simple (σ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.

U2 - 10.1142/S0129054116500143

DO - 10.1142/S0129054116500143

M3 - Article

SN - 0129-0541

VL - 27

SP - 529

EP - 543

JO - INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE

JF - INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE

IS - 5

ER -

Algorithms for Longest Common Abelian Factors

Abstract

Access to Document

Fingerprint

Cite this