TY - GEN

T1 - Full-fledged real-time indexing for constant size alphabets

AU - Kucherov, Gregory

AU - Nekrich, Yakov

PY - 2013

Y1 - 2013

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

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

UR - http://www.scopus.com/inward/record.url?scp=84880262603&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-39206-1_55

DO - 10.1007/978-3-642-39206-1_55

M3 - Conference contribution

AN - SCOPUS:84880262603

SN - 9783642392054

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 650

EP - 660

BT - Automata, Languages, and Programming - 40th International Colloquium, ICALP 2013, Proceedings

T2 - 40th International Colloquium on Automata, Languages, and Programming, ICALP 2013

Y2 - 8 July 2013 through 12 July 2013

ER -