Full-Fledged Real-Time Indexing for Constant Size Alphabets

In this paper we describe a data structure that supports pattern matching queries on a dynamically arriving text over an alphabet of constant size. Each new symbol can be prepended to T in O(1) worst‐case time. At any moment, we can report all occurrences of a pattern P in the current text in $O(|P|+k)$ time, where |P| is the length of P and k is the number of occurrences. This resolves, under assumption of constant size alphabet, a long‐standing open problem of existence of a real‐time indexing method for string matching (see Amir and Nor in Real‐time indexing over fixed finite alphabets, pp. 1086–1095, 2008).