Optimal On-Line Search and Sublinear Time Update in String Matching

DOI10.1137/S0097539795286119zbMath0911.68044OpenAlexW2158630342MaRDI QIDQ4388896

Roberto Grossi, Paolo Ferragina

Publication date: 10 May 1998

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0097539795286119

zbMATH Keywords

string matchingsuffix treedynamic data structurestext indexing

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Parallel algorithms in computer science (68W10) Data structures (68P05) Information storage and retrieval of data (68P20)

Related Items (4)

Online timestamped text indexing ⋮ Semi-dynamic Compact Index for Short Patterns and Succinct van Emde Boas Tree ⋮ Dynamic and internal longest common substring ⋮ Longest common substring made fully dynamic

This page was built for publication: Optimal On-Line Search and Sublinear Time Update in String Matching