Longest Palindromic Substring in Sublinear Time

Panagiotis Charalampopoulos; Solon P. Pissis; Jakub Radoszewski

doi:10.4230/LIPIcs.CPM.2022.20

Longest Palindromic Substring in Sublinear Time

Panagiotis Charalampopoulos^*, Solon P. Pissis, Jakub Radoszewski

^*Corresponding author for this work

Research output: Chapter in Book / Report / Conference proceeding › Conference contribution › Academic › peer-review

Abstract

We revisit the classic algorithmic problem of computing a longest palidromic substring. This problem is solvable by a celebrated O(n)-time algorithm [Manacher, J. ACM 1975], where n is the length of the input string. For small alphabets, O(n) is not necessarily optimal in the word RAM model of computation: a string of length n over alphabet [0, σ) can be stored in O(n log σ/log n) space and read in O(n log σ/log n) time. We devise a simple O(n log σ/log n)-time algorithm for computing a longest palindromic substring. In particular, our algorithm works in sublinear time if σ = 2^o(log n). Our technique relies on periodicity and on the O(n log σ/log n)-time constructible data structure of Kempa and Kociumaka [STOC 2019] that answers longest common extension queries in O(1) time.

Original language	English
Title of host publication	33rd Annual Symposium on Combinatorial Pattern Matching (CPM 2022)
Editors	Hideo Bannai, Jan Holub
Publisher	Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Chapter	20
Pages	1-9
Number of pages	9
ISBN (Electronic)	9783959772341
DOIs	https://doi.org/10.4230/LIPIcs.CPM.2022.20
Publication status	Published - 2022
Event	33rd Annual Symposium on Combinatorial Pattern Matching, CPM 2022 - Prague, Czech Republic Duration: 27 Jun 2022 → 29 Jun 2022

Publication series

Name	Leibniz International Proceedings in Informatics, LIPIcs
Volume	223
ISSN (Print)	1868-8969

Conference

Conference	33rd Annual Symposium on Combinatorial Pattern Matching, CPM 2022
Country/Territory	Czech Republic
City	Prague
Period	27/06/22 → 29/06/22

Bibliographical note

Funding Information:
Panagiotis Charalampopoulos: Supported by the Israel Science Foundation, grant no. 810/21. Solon P. Pissis: Supported by the PANGAIA and ALPACA projects that have received funding from the European Union's Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreements No 872539 and 956229, respectively. Jakub Radoszewski: Supported by the Polish National Science Center, grant no. 2018/31/D/ST6/03991.

Funding Information:
Funding Panagiotis Charalampopoulos: Supported by the Israel Science Foundation, grant no. 810/21. Solon P. Pissis: Supported by the PANGAIA and ALPACA projects that have received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreements No 872539 and 956229, respectively. Jakub Radoszewski: Supported by the Polish National Science Center, grant no. 2018/31/D/ST6/ 03991.

Publisher Copyright:
© Panagiotis Charalampopoulos, Solon P. Pissis, and Jakub Radoszewski; licensed under Creative Commons License CC-BY 4.0

Keywords

longest common extension
longest palindromic substring
string algorithms

Access to Document

10.4230/LIPIcs.CPM.2022.20

Persistent URL (handle)

Copy link address

Cite this

Charalampopoulos, P., Pissis, S. P., & Radoszewski, J. (2022). Longest Palindromic Substring in Sublinear Time. In H. Bannai, & J. Holub (Eds.), 33rd Annual Symposium on Combinatorial Pattern Matching (CPM 2022) (pp. 1-9). (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 223). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.CPM.2022.20

Charalampopoulos, Panagiotis ; Pissis, Solon P. ; Radoszewski, Jakub. / Longest Palindromic Substring in Sublinear Time. 33rd Annual Symposium on Combinatorial Pattern Matching (CPM 2022). editor / Hideo Bannai ; Jan Holub. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2022. pp. 1-9 (Leibniz International Proceedings in Informatics, LIPIcs).

@inproceedings{c39a26570d4e4c0ebc2a6c386f78d8fd,

title = "Longest Palindromic Substring in Sublinear Time",

abstract = "We revisit the classic algorithmic problem of computing a longest palidromic substring. This problem is solvable by a celebrated O(n)-time algorithm [Manacher, J. ACM 1975], where n is the length of the input string. For small alphabets, O(n) is not necessarily optimal in the word RAM model of computation: a string of length n over alphabet [0, σ) can be stored in O(n log σ/log n) space and read in O(n log σ/log n) time. We devise a simple O(n log σ/log n)-time algorithm for computing a longest palindromic substring. In particular, our algorithm works in sublinear time if σ = 2o(log n). Our technique relies on periodicity and on the O(n log σ/log n)-time constructible data structure of Kempa and Kociumaka [STOC 2019] that answers longest common extension queries in O(1) time.",

keywords = "longest common extension, longest palindromic substring, string algorithms",

author = "Panagiotis Charalampopoulos and Pissis, {Solon P.} and Jakub Radoszewski",

note = "Funding Information: Panagiotis Charalampopoulos: Supported by the Israel Science Foundation, grant no. 810/21. Solon P. Pissis: Supported by the PANGAIA and ALPACA projects that have received funding from the European Union's Horizon 2020 research and innovation programme under the Marie Sk{\l}odowska-Curie grant agreements No 872539 and 956229, respectively. Jakub Radoszewski: Supported by the Polish National Science Center, grant no. 2018/31/D/ST6/03991. Funding Information: Funding Panagiotis Charalampopoulos: Supported by the Israel Science Foundation, grant no. 810/21. Solon P. Pissis: Supported by the PANGAIA and ALPACA projects that have received funding from the European Union{\textquoteright}s Horizon 2020 research and innovation programme under the Marie Sk{\l}odowska-Curie grant agreements No 872539 and 956229, respectively. Jakub Radoszewski: Supported by the Polish National Science Center, grant no. 2018/31/D/ST6/ 03991. Publisher Copyright: {\textcopyright} Panagiotis Charalampopoulos, Solon P. Pissis, and Jakub Radoszewski; licensed under Creative Commons License CC-BY 4.0; 33rd Annual Symposium on Combinatorial Pattern Matching, CPM 2022 ; Conference date: 27-06-2022 Through 29-06-2022",

year = "2022",

doi = "10.4230/LIPIcs.CPM.2022.20",

language = "English",

series = "Leibniz International Proceedings in Informatics, LIPIcs",

publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",

pages = "1--9",

editor = "Hideo Bannai and Jan Holub",

booktitle = "33rd Annual Symposium on Combinatorial Pattern Matching (CPM 2022)",

}

Charalampopoulos, P, Pissis, SP & Radoszewski, J 2022, Longest Palindromic Substring in Sublinear Time. in H Bannai & J Holub (eds), 33rd Annual Symposium on Combinatorial Pattern Matching (CPM 2022). Leibniz International Proceedings in Informatics, LIPIcs, vol. 223, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, pp. 1-9, 33rd Annual Symposium on Combinatorial Pattern Matching, CPM 2022, Prague, Czech Republic, 27/06/22. https://doi.org/10.4230/LIPIcs.CPM.2022.20

Longest Palindromic Substring in Sublinear Time. / Charalampopoulos, Panagiotis; Pissis, Solon P.; Radoszewski, Jakub.
33rd Annual Symposium on Combinatorial Pattern Matching (CPM 2022). ed. / Hideo Bannai; Jan Holub. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2022. p. 1-9 (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 223).

Research output: Chapter in Book / Report / Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Longest Palindromic Substring in Sublinear Time

AU - Charalampopoulos, Panagiotis

AU - Pissis, Solon P.

AU - Radoszewski, Jakub

N1 - Funding Information: Panagiotis Charalampopoulos: Supported by the Israel Science Foundation, grant no. 810/21. Solon P. Pissis: Supported by the PANGAIA and ALPACA projects that have received funding from the European Union's Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreements No 872539 and 956229, respectively. Jakub Radoszewski: Supported by the Polish National Science Center, grant no. 2018/31/D/ST6/03991. Funding Information: Funding Panagiotis Charalampopoulos: Supported by the Israel Science Foundation, grant no. 810/21. Solon P. Pissis: Supported by the PANGAIA and ALPACA projects that have received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreements No 872539 and 956229, respectively. Jakub Radoszewski: Supported by the Polish National Science Center, grant no. 2018/31/D/ST6/ 03991. Publisher Copyright: © Panagiotis Charalampopoulos, Solon P. Pissis, and Jakub Radoszewski; licensed under Creative Commons License CC-BY 4.0

PY - 2022

Y1 - 2022

N2 - We revisit the classic algorithmic problem of computing a longest palidromic substring. This problem is solvable by a celebrated O(n)-time algorithm [Manacher, J. ACM 1975], where n is the length of the input string. For small alphabets, O(n) is not necessarily optimal in the word RAM model of computation: a string of length n over alphabet [0, σ) can be stored in O(n log σ/log n) space and read in O(n log σ/log n) time. We devise a simple O(n log σ/log n)-time algorithm for computing a longest palindromic substring. In particular, our algorithm works in sublinear time if σ = 2o(log n). Our technique relies on periodicity and on the O(n log σ/log n)-time constructible data structure of Kempa and Kociumaka [STOC 2019] that answers longest common extension queries in O(1) time.

AB - We revisit the classic algorithmic problem of computing a longest palidromic substring. This problem is solvable by a celebrated O(n)-time algorithm [Manacher, J. ACM 1975], where n is the length of the input string. For small alphabets, O(n) is not necessarily optimal in the word RAM model of computation: a string of length n over alphabet [0, σ) can be stored in O(n log σ/log n) space and read in O(n log σ/log n) time. We devise a simple O(n log σ/log n)-time algorithm for computing a longest palindromic substring. In particular, our algorithm works in sublinear time if σ = 2o(log n). Our technique relies on periodicity and on the O(n log σ/log n)-time constructible data structure of Kempa and Kociumaka [STOC 2019] that answers longest common extension queries in O(1) time.

KW - longest common extension

KW - longest palindromic substring

KW - string algorithms

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

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

U2 - 10.4230/LIPIcs.CPM.2022.20

DO - 10.4230/LIPIcs.CPM.2022.20

M3 - Conference contribution

AN - SCOPUS:85134332505

T3 - Leibniz International Proceedings in Informatics, LIPIcs

SP - 1

EP - 9

BT - 33rd Annual Symposium on Combinatorial Pattern Matching (CPM 2022)

A2 - Bannai, Hideo

A2 - Holub, Jan

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

T2 - 33rd Annual Symposium on Combinatorial Pattern Matching, CPM 2022

Y2 - 27 June 2022 through 29 June 2022

ER -

Charalampopoulos P, Pissis SP, Radoszewski J. Longest Palindromic Substring in Sublinear Time. In Bannai H, Holub J, editors, 33rd Annual Symposium on Combinatorial Pattern Matching (CPM 2022). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. 2022. p. 1-9. (Leibniz International Proceedings in Informatics, LIPIcs). Epub 2022 Jun 22. doi: 10.4230/LIPIcs.CPM.2022.20

Longest Palindromic Substring in Sublinear Time

Abstract

Publication series

Conference

Bibliographical note

Keywords

Access to Document

Persistent URL (handle)

Other files and links

Fingerprint

Cite this