Longest previous overlapping factor array

Hideo Bannai; Shunsuke Inenaga; Neerja Mhaskar

doi:10.1016/j.ipl.2021.106097

Longest previous overlapping factor array

Hideo Bannai, Shunsuke Inenaga, Neerja Mhaskar

Mathematical Informatics

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

1 Citation (Scopus)

Abstract

In this paper, we introduce the longest previous overlapping factor array of a string – a variant of the longest previous factor array. We show that it can be computed in linear time in the length of the input string, via a reduction to the Max-variant of the Manhattan skyline problem Crochemore et al. (2014) [5].

Original language	English
Article number	106097
Journal	Information Processing Letters
Volume	168
DOIs	https://doi.org/10.1016/j.ipl.2021.106097
Publication status	Published - Jun 2021

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Signal Processing
Information Systems
Computer Science Applications

Access to Document

10.1016/j.ipl.2021.106097

Cite this

@article{d4749a762560486190f6983fbc76c4fe,

title = "Longest previous overlapping factor array",

abstract = "In this paper, we introduce the longest previous overlapping factor array of a string – a variant of the longest previous factor array. We show that it can be computed in linear time in the length of the input string, via a reduction to the Max-variant of the Manhattan skyline problem Crochemore et al. (2014) [5].",

keywords = "Algorithms, Longest previous overlapping factor, Manhattan skyline problem, Overlapping factor",

author = "Hideo Bannai and Shunsuke Inenaga and Neerja Mhaskar",

note = "Publisher Copyright: {\textcopyright} 2021 Elsevier B.V.",

year = "2021",

month = jun,

doi = "10.1016/j.ipl.2021.106097",

language = "English",

volume = "168",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier B.V.",

}

TY - JOUR

T1 - Longest previous overlapping factor array

AU - Bannai, Hideo

AU - Inenaga, Shunsuke

AU - Mhaskar, Neerja

PY - 2021/6

Y1 - 2021/6

N2 - In this paper, we introduce the longest previous overlapping factor array of a string – a variant of the longest previous factor array. We show that it can be computed in linear time in the length of the input string, via a reduction to the Max-variant of the Manhattan skyline problem Crochemore et al. (2014) [5].

AB - In this paper, we introduce the longest previous overlapping factor array of a string – a variant of the longest previous factor array. We show that it can be computed in linear time in the length of the input string, via a reduction to the Max-variant of the Manhattan skyline problem Crochemore et al. (2014) [5].

KW - Algorithms

KW - Longest previous overlapping factor

KW - Manhattan skyline problem

KW - Overlapping factor

UR - http://www.scopus.com/inward/record.url?scp=85099789911&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85099789911&partnerID=8YFLogxK

U2 - 10.1016/j.ipl.2021.106097

DO - 10.1016/j.ipl.2021.106097

M3 - Article

AN - SCOPUS:85099789911

SN - 0020-0190

VL - 168

JO - Information Processing Letters

JF - Information Processing Letters

M1 - 106097

ER -

Longest previous overlapping factor array

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Cite this