Artykuł w czasopiśmie
Brak miniatury
Licencja
CC-BY - Uznanie autorstwaLongest Palindromic Substring in Sublinear Time
| cris.lastimport.scopus | 2024-02-12T20:20:33Z |
| dc.abstract.en | We revisit the classic algorithmic problem of computing a longest palidromic substring. This problem is solvable by a celebrated (n)-time algorithm [Manacher, J. ACM 1975], where n is the length of the input string. For small alphabets, (n) is not necessarily optimal in the word RAM model of computation: a string of length n over alphabet [0,σ) can be stored in (n log σ/log n) space and read in (n log σ/log n) time. We devise a simple (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 (n log σ/log n)-time constructible data structure of Kempa and Kociumaka [STOC 2019] that answers longest common extension queries in (1) time. |
| dc.affiliation | Uniwersytet Warszawski |
| dc.conference.country | Czechy |
| dc.conference.datefinish | 2022-06-29 |
| dc.conference.datestart | 2022-06-27 |
| dc.conference.place | Praga |
| dc.conference.series | Combinatorial Pattern Matching |
| dc.conference.series | Combinatorial Pattern Matching |
| dc.conference.seriesshortcut | CPM |
| dc.conference.shortcut | CPM 2022 |
| dc.conference.weblink | https://www.stringology.org/event/CPM2022/ |
| dc.contributor.author | Radoszewski, Jakub |
| dc.contributor.author | Pissis, Solon P. |
| dc.contributor.author | Charalampopoulos, Panagiotis |
| dc.date.accessioned | 2024-01-25T05:16:00Z |
| dc.date.available | 2024-01-25T05:16:00Z |
| dc.date.copyright | 2022-06-22 |
| dc.date.issued | 2022 |
| dc.description.accesstime | AT_PUBLICATION |
| dc.description.finance | Publikacja bezkosztowa |
| dc.description.version | FINAL_PUBLISHED |
| dc.identifier.doi | 10.4230/LIPICS.CPM.2022.20 |
| dc.identifier.uri | https://repozytorium.uw.edu.pl//handle/item/111470 |
| dc.identifier.weblink | https://drops.dagstuhl.de/opus/volltexte/2022/16147/ |
| dc.language | eng |
| dc.pbn.affiliation | computer and information sciences |
| dc.relation.pages | 20:1--20:9 |
| dc.rights | CC-BY |
| dc.sciencecloud | nosend |
| dc.subject.en | string algorithms |
| dc.subject.en | longest palindromic substring |
| dc.subject.en | longest common extension |
| dc.title | Longest Palindromic Substring in Sublinear Time |
| dc.type | JournalArticle |
| dspace.entity.type | Publication |