On the Exact Complexity of String Matching: Upper Bounds

DOI10.1137/0221028zbMATH Open0761.68046OpenAlexW4239658213MaRDI QIDQ4016906FDOQ4016906

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

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

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)

Cited In (22)

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