Skip to Main content Skip to Navigation
Journal articles

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 metadata
Contributor : Gregory Kucherov Connect in order to contact the contributor
Submitted on : Tuesday, May 29, 2018 - 11:44:34 PM
Last modification on : Saturday, January 15, 2022 - 3:56:27 AM

Links full text



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⟩



Record views