Full-Fledged Real-Time Indexing for Constant Size Alphabets - Archive ouverte HAL Accéder directement au contenu
Article Dans Une Revue Algorithmica Année : 2017

Full-Fledged Real-Time Indexing for Constant Size Alphabets

Résumé

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).

Dates et versions

hal-01802943 , version 1 (29-05-2018)

Identifiants

Citer

Gregory Kucherov, Yakov Nekrich. Full-Fledged Real-Time Indexing for Constant Size Alphabets. Algorithmica, 2017, 79 (2), pp.387-400. ⟨10.1007/s00453-016-0199-7⟩. ⟨hal-01802943⟩
55 Consultations
0 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More