pipette
ENEnglish

Longest Unbordered Factors in Linear Time

Takuya Mieno

Preprint

En palabras de los autores

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.

Resultado principalLimitación que admiten los autores

Apareció: martes, 10 de noviembre. arXiv. Preprint, todavía sin revisión por pares.