2022-06-22
Longest palindromic substring in sublinear time
Publication
Publication
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.
| Additional Metadata | |
|---|---|
| , , | |
| doi.org/10.4230/LIPIcs.CPM.2022.20 | |
| Leibniz International Proceedings in Informatics (LIPIcs) | |
| 33rd Annual Symposium on Combinatorial Pattern Matching, CPM 2022 | |
| Organisation | Centrum Wiskunde & Informatica, Amsterdam (CWI), The Netherlands |
|
Charalampopoulos, P., Pissis, S., & Radoszewski, J. (2022). Longest palindromic substring in sublinear time. In Annual Symposium on Combinatorial Pattern Matching (pp. 20:1–20:9). doi:10.4230/LIPIcs.CPM.2022.20 |
|
