Full-Fledged Real-Time Indexing for Constant Size Alphabets

Abstract : 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).
Document type :
Journal articles
Complete list of metadatas

https://hal-upec-upem.archives-ouvertes.fr/hal-01802943
Contributor : Gregory Kucherov <>
Submitted on : Tuesday, May 29, 2018 - 11:44:34 PM
Last modification on : Thursday, July 5, 2018 - 2:45:35 PM

Links full text

Identifiers

Citation

Gregory Kucherov, Yakov Nekrich. Full-Fledged Real-Time Indexing for Constant Size Alphabets. Algorithmica, Springer Verlag, 2017, 79 (2), pp.387-400. ⟨10.1007/s00453-016-0199-7⟩. ⟨hal-01802943⟩

Share

Metrics

Record views

114