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

DOI10.1137/S0097539795286119MaRDI QIDQ4388896zbMATH OpenOpenAlexFDO

Authors Paolo Ferragina, Roberto Grossi

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

dynamic data structuresstring matchingsuffix treetext indexing

Mathematics Subject Classification ID

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

Recommendations

• Dynamic Text Indexing under String Updates
• scientific article; zbMATH DE number 1445383
• Dynamic text and static pattern matching.

Cited in

(12)

• Efficient online string matching based on characters distance text sampling
• Dynamic and internal longest common substring
• Dynamic string searching
• The exact online string matching problem: a review of the most recent results
• Semi-dynamic compact index for short patterns and succinct van Emde Boas tree
• Online timestamped text indexing
• Space Lower Bounds for Online Pattern Matching
• Space lower bounds for online pattern matching
• Longest common substring made fully dynamic
• Searching for a modified pattern in a changing text
• Online algorithms for finding distinct substrings with length and multiple prefix and suffix conditions
• On-line approximate string matching with bounded errors

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4388896)