跳到正文
研踪PaperTrail
← 研踪 PaperTrail

arXiv:2611.12146 · v1

Longest Unbordered Factors in Linear Time

首次提交 2026-11-09 17:55
版本更新 2026-11-09 17:55
雷达观测 2026-11-10 15:22
arXiv ↗PDF ↗

摘要

A border of a string is a nonempty proper prefix that is also a suffix. A string is unbordered if it has no border. The length of a longest unbordered factor is closely related to the smallest period of the string. While the smallest period can be computed in linear time, the best previously known algorithm for computing a longest unbordered factor takes O(nlog⁡n)O(n \log n) worst-case time for a string of length nn. Whether this computational problem can be solved in worst-case linear time has remained open. In this paper, we resolve this open problem for integer alphabets of size nO(1)n^{O(1)} by presenting an algorithm that computes all occurrences of longest unbordered factors in O(n)O(n) worst-case time. Our algorithm uses a combinatorial property of longest unbordered factors and scans the input string in both directions to capture all occurrences achieving the global maximum without computing the local maximum at every starting position.

AI 论文解读

基于摘要 · 非全文审阅

此版本尚未生成 AI 解读。解读由后台任务生成并按论文版本保存,登录后共享已有结果。

版本差异

目前只收录了一个版本。收录下一版后,可以对照标题、作者、分类和摘要。

观测到的版本

相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。

v1 · 2026-11-09 17:55 · 最新观测版本

Longest Unbordered Factors in Linear Time

A border of a string is a nonempty proper prefix that is also a suffix. A string is unbordered if it has no border. The length of a longest unbordered factor is closely related to the smallest period of the string. While the smallest period can be computed in linear time, the best previously known algorithm for computing a longest unbordered factor takes O(nlog⁡n)O(n \log n) worst-case time for a string of length nn. Whether this computational problem can be solved in worst-case linear time has remained open. In this paper, we resolve this open problem for integer alphabets of size nO(1)n^{O(1)} by presenting an algorithm that computes all occurrences of longest unbordered factors in O(n)O(n) worst-case time. Our algorithm uses a combinatorial property of longest unbordered factors and scans the input string in both directions to capture all occurrences achieving the global maximum without computing the local maximum at every starting position.

查看此版本解读 →查看此版本原文 ↗