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

string matchingdynamic data structuressuffix treetext indexing

Mathematics Subject Classification ID

Information storage and retrieval of data (68P20) Analysis of algorithms and problem complexity (68Q25) Data structures (68P05) 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)

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

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)