文章基本信息

标题：Computing Runs on a Trie
本地全文：下载
作者：Ryo Sugahara ; Yuto Nakashima ; Shunsuke Inenaga 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2019
卷号：128
页码：1-11
DOI：10.4230/LIPIcs.CPM.2019.23
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：A maximal repetition, or run, in a string, is a maximal periodic substring whose smallest period is at most half the length of the substring. In this paper, we consider runs that correspond to a path on a trie, or in other words, on a rooted edge-labeled tree where the endpoints of the path must be a descendant/ancestor of the other. For a trie with n edges, we show that the number of runs is less than n. We also show an O(n sqrt{log n}log log n) time and O(n) space algorithm for counting and finding the shallower endpoint of all runs. We further show an O(n log n) time and O(n) space algorithm for finding both endpoints of all runs. We also discuss how to improve the running time even more.
关键词：runs; Lyndon words