← 研踪 PaperTrailarXiv:2611.13950 · v1
Real-Time String Indexing in Optimal Time
首次提交 2026-11-10 19:38
版本更新 2026-11-10 19:38
雷达观测 2026-11-11 11:04
摘要
In this paper we describe the first fully real-time indexing solution for pattern matching over an arbitrary integer alphabet. Our data structure spends worst-case time w.h.p. for processing each new letter appended to and worst-case time for reporting all occurrences of , where and are strings over an integer alphabet. The main idea of our solution is a novel representation of the suffix tree, the path-decomposed suffix tree, which does not store the full topology of the suffix tree but instead decomposes it into paths, each stored in a dictionary that encodes parent--child relationships indirectly.
作者备注:30 pages, 7 figures
观测到的版本
相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。
v1 · 2026-11-10 19:38 · 最新观测版本
Real-Time String Indexing in Optimal Time
In this paper we describe the first fully real-time indexing solution for pattern matching over an arbitrary integer alphabet. Our data structure spends worst-case time w.h.p. for processing each new letter appended to and worst-case time for reporting all occurrences of , where and are strings over an integer alphabet. The main idea of our solution is a novel representation of the suffix tree, the path-decomposed suffix tree, which does not store the full topology of the suffix tree but instead decomposes it into paths, each stored in a dictionary that encodes parent--child relationships indirectly.
查看此版本解读 →查看此版本原文 ↗