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 $O(1)$ worst-case time w.h.p. for processing each new letter appended to T and worst-case $O(|P|+occ)$ time for reporting all occurrences of P, where T and P 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.