2026-07-22T22:30:53Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10018 2024-03-06T10:45:21Z ddc:004 open_access

Longest Unbordered Factor in Quasilinear Time Kociumaka, Tomasz Kundu, Ritu Mohamed, Manal Pissis, Solon P. longest unbordered factor factorisation period border strings A border u of a word w is a proper factor of w occurring both as a prefix and as a suffix. The maximal unbordered factor of w is the longest factor of w which does not have a border. Here an O(n log n)-time with high probability (or O(n log n log^2 log n)-time deterministic) algorithm to compute the Longest Unbordered Factor Array of w for general alphabets is presented, where n is the length of w. This array specifies the length of the maximal unbordered factor starting at each position of w. This is a major improvement on the running time of the currently best worst-case algorithm working in O(n^{1.5}) time for integer alphabets [Gawrychowski et al., 2015]. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Tomasz Kociumaka and Ritu Kundu and Manal Mohamed and Solon P. Pissis 2018 Is Part Of LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2018.70 urn:nbn:de:0030-drops-100184 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.70 eng https://creativecommons.org/licenses/by/3.0/legalcode