Full-fledged real-time indexing for constant size alphabets

Gregory Kucherov, Yakov Nekrich

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

1 Citation (Scopus)

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) expected 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 [2]).

Original languageEnglish
Title of host publicationAutomata, Languages, and Programming - 40th International Colloquium, ICALP 2013, Proceedings
Pages650-660
Number of pages11
EditionPART 1
DOIs
Publication statusPublished - 2013
Externally publishedYes
Event40th International Colloquium on Automata, Languages, and Programming, ICALP 2013 - Riga, Latvia
Duration: 8 Jul 201312 Jul 2013

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
NumberPART 1
Volume7965 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference40th International Colloquium on Automata, Languages, and Programming, ICALP 2013
Country/TerritoryLatvia
CityRiga
Period8/07/1312/07/13

Fingerprint

Dive into the research topics of 'Full-fledged real-time indexing for constant size alphabets'. Together they form a unique fingerprint.

Cite this