Real-time string matching in sublinear space

Leszek Ga̧sieniec; Roman Kolpakov

doi:10.1007/978-3-540-27801-6_9

Real-time string matching in sublinear space

Leszek Ga̧sieniec, Roman Kolpakov

Research output: Chapter in Book/Report/Conference proceeding › Chapter

4 Scopus citations

Abstract

We study a problem of efficient utilisation of extra memory space in real-time string matching. We propose, for any constant ε > 0, a real-time string matching algorithm claiming O(m^ε) extra space, where m is the size of a pattern. All previously known real-time string matching algorithms use Ω(m) extra space.

Original language	English (US)
Title of host publication	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Editors	Suleyman Cenk Sahinalp, S. Muthukrishnan, Ugur Dogrusoz
Publisher	Springer Verlag
Pages	117-129
Number of pages	13
ISBN (Print)	354022341X, 9783540223412
DOIs	https://doi.org/10.1007/978-3-540-27801-6_9
State	Published - 2004
Externally published	Yes

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	3109
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-540-27801-6_9

Cite this

Ga̧sieniec, L., & Kolpakov, R. (2004). Real-time string matching in sublinear space. In S. C. Sahinalp, S. Muthukrishnan, & U. Dogrusoz (Eds.), Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (pp. 117-129). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 3109). Springer Verlag. https://doi.org/10.1007/978-3-540-27801-6_9

Real-time string matching in sublinear space. / Ga̧sieniec, Leszek; Kolpakov, Roman.
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). ed. / Suleyman Cenk Sahinalp; S. Muthukrishnan; Ugur Dogrusoz. Springer Verlag, 2004. p. 117-129 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 3109).

Research output: Chapter in Book/Report/Conference proceeding › Chapter

Ga̧sieniec, L & Kolpakov, R 2004, Real-time string matching in sublinear space. in SC Sahinalp, S Muthukrishnan & U Dogrusoz (eds), Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 3109, Springer Verlag, pp. 117-129. https://doi.org/10.1007/978-3-540-27801-6_9

Ga̧sieniec L, Kolpakov R. Real-time string matching in sublinear space. In Sahinalp SC, Muthukrishnan S, Dogrusoz U, editors, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Springer Verlag. 2004. p. 117-129. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-540-27801-6_9

Ga̧sieniec, Leszek ; Kolpakov, Roman. / Real-time string matching in sublinear space. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). editor / Suleyman Cenk Sahinalp ; S. Muthukrishnan ; Ugur Dogrusoz. Springer Verlag, 2004. pp. 117-129 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inbook{3259cc426d4d4b808c16cb492ff2e2b3,

title = "Real-time string matching in sublinear space",

abstract = "We study a problem of efficient utilisation of extra memory space in real-time string matching. We propose, for any constant ε > 0, a real-time string matching algorithm claiming O(mε) extra space, where m is the size of a pattern. All previously known real-time string matching algorithms use Ω(m) extra space.",

author = "Leszek G{\c a}sieniec and Roman Kolpakov",

year = "2004",

doi = "10.1007/978-3-540-27801-6_9",

language = "English (US)",

isbn = "354022341X",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "117--129",

editor = "Sahinalp, {Suleyman Cenk} and S. Muthukrishnan and Ugur Dogrusoz",

booktitle = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

}

TY - CHAP

T1 - Real-time string matching in sublinear space

AU - Ga̧sieniec, Leszek

AU - Kolpakov, Roman

PY - 2004

Y1 - 2004

N2 - We study a problem of efficient utilisation of extra memory space in real-time string matching. We propose, for any constant ε > 0, a real-time string matching algorithm claiming O(mε) extra space, where m is the size of a pattern. All previously known real-time string matching algorithms use Ω(m) extra space.

AB - We study a problem of efficient utilisation of extra memory space in real-time string matching. We propose, for any constant ε > 0, a real-time string matching algorithm claiming O(mε) extra space, where m is the size of a pattern. All previously known real-time string matching algorithms use Ω(m) extra space.

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

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

U2 - 10.1007/978-3-540-27801-6_9

DO - 10.1007/978-3-540-27801-6_9

M3 - Chapter

AN - SCOPUS:35048839249

SN - 354022341X

SN - 9783540223412

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

SP - 117

EP - 129

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

A2 - Sahinalp, Suleyman Cenk

A2 - Muthukrishnan, S.

A2 - Dogrusoz, Ugur

PB - Springer Verlag

ER -

Real-time string matching in sublinear space

Abstract

Publication series

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this