← 研踪 PaperTrailarXiv:2611.12146 · v1
Longest Unbordered Factors in Linear Time
首次提交 2026-11-09 17:55
版本更新 2026-11-09 17:55
雷达观测 2026-11-10 15:22
摘要
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 worst-case time for a string of length . 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 by presenting an algorithm that computes all occurrences of longest unbordered factors in 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.
观测到的版本
相邻记录可能跳过中间版本;首次发现 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 worst-case time for a string of length . 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 by presenting an algorithm that computes all occurrences of longest unbordered factors in 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.
查看此版本解读 →查看此版本原文 ↗