On the Exact Complexity of String Matching: Upper Bounds

DOI10.1137/0221028MaRDI QIDQ4016906zbMATH OpenOpenAlexFDO

Authors Zvi Galil, R. Giancarlo

Publication date 16 January 1993

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

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

zbMATH Keywords

string matchingstring searchingworst case behaviortext editing

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Parallel algorithms in computer science (68W10) Computing methodologies for text processing; mathematical typography (68U15)

Recommendations

• Tighter Lower Bounds on the Exact Complexity of String Matching
• Exact bounds on the complexity of sequential string matching algorithms
• Tighter Upper Bounds on the Exact Complexity of String Matching
• On Simon's string searching algorithm
• Efficient comparison based string matching

Cited in

(22)

• A simple fast hybrid pattern-matching algorithm
• scientific article; zbMATH DE number 1256698 (Why is no real title available?)
• \(k\) one-way heads cannot do string-matching
• Exact bounds on the complexity of sequential string matching algorithms
• Average complexity of backward \(q\)-gram string matching algorithms
• Tight comparison bounds for the string prefix-matching problem
• Tight bounds on the complexity of the Apostolico-Giancarlo algorithm
• Tighter Lower Bounds on the Exact Complexity of String Matching
• Efficient comparison based string matching
• Sorting signed permutations by tandem duplication random loss and inverse tandem duplication random loss
• Fast string matching for DNA sequences
• The exact online string matching problem: a review of the most recent results
• How the character comparison order shapes the shift function of on-line pattern matching algorithms
• scientific article; zbMATH DE number 5790350 (Why is no real title available?)
• scientific article; zbMATH DE number 7651042 (Why is no real title available?)
• On Hardness of Several String Indexing Problems
• On Simon's string searching algorithm
• Light-based string matching
• Saving comparisons in the Crochemore-Perrin string-matching algorithm
• Looking for MUM and DAD: text-text comparisons do help
• Improved pattern-scan-order algorithms for string matching
• A New String Matching Algorithm

This page was built for publication: On the Exact Complexity of String Matching: Upper Bounds

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