Time–space trade-offs for longest common extensions

Autor: Bille, Philip ^a, Gørtz, Inge Li ^a, Sach, Benjamin ^b, Vildhøj, Hjalte Wedel ^{a, ⁎}

Publikováno v: In Journal of Discrete Algorithms March 2014 25:42-50

Longest Palindromic Substring in Sublinear Time

Autor: Charalampopoulos, Panagiotis, Pissis, Solon P., Radoszewski, Jakub, Bannai, Hideo, Holub, Jan

Publikováno v: 33rd Annual Symposium on Combinatorial Pattern Matching (CPM 2022), 1-9
STARTPAGE=1;ENDPAGE=9;TITLE=33rd Annual Symposium on Combinatorial Pattern Matching (CPM 2022)
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) . 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
33rd Annual Symposium on Combinatorial Pattern Matching (CPM)
33rd Annual Symposium on Combinatorial Pattern Matching (CPM), 2022, Prague, Czech Republic. ⟨10.4230/LIPIcs.CPM.2022.20⟩

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) i

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::36afe39d95c9adf0160ec66f5ff66ae1
https://doi.org/10.4230/LIPIcs.CPM.2022.20

The longest common extension problem revisited and applications to approximate string searching

Autor: Ilie, Lucian ^{a, ⁎, 1}, Navarro, Gonzalo ^{b, 2}, Tinta, Liviu ^a

Publikováno v: In Journal of Discrete Algorithms 2010 8(4):418-428

Linear Time Runs over General Ordered Alphabets

Autor: Ellert, Jonas, Fischer, Johannes

A run in a string is a maximal periodic substring. For example, the string bananatree contains the runs anana = (an)^{5/2} and ee = e². There are less than n runs in any length-n string, and computing all runs for a string over a linearly-sortable a

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::8adf7ff93249fbfdc73eb600899249bf
http://arxiv.org/abs/2102.08670

Tight lower bounds for the longest common extension problem

Autor: Kosolobov, Dmitry

Publikováno v: In Information Processing Letters September 2017 125:26-29