Full-Fledged Real-Time Indexing for Constant Size Alphabets

Gregory Kucherov, Yakov Nekrich

Research output: Contribution to journalArticlepeer-review

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

Original languageEnglish
Pages (from-to)387-400
Number of pages14
JournalAlgorithmica (New York)
Volume79
Issue number2
DOIs
Publication statusPublished - 1 Oct 2017
Externally publishedYes

Keywords

  • Data Structures
  • Pattern matching
  • Real-time indexing
  • Text indexing

Fingerprint

Dive into the research topics of 'Full-Fledged Real-Time Indexing for Constant Size Alphabets'. Together they form a unique fingerprint.

Cite this