Tight comparison bounds for the string prefix-matching problem

DOI10.1016/0020-0190(93)90156-4zbMath0802.68066OpenAlexW2048532915MaRDI QIDQ685487

Livio Colussi, Laura Toniolo, Dany Breslauer

Publication date: 11 December 1994

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://ir.cwi.nl/pub/1524

zbMATH Keywords

string matchingpatternsprefix matching

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorics on words (68R15)

Related Items (2)

Optimal parallel algorithms for Prefix Matching ⋮ How the character comparison order shapes the shift function of on-line pattern matching algorithms

Cites Work

• Correctness and efficiency of pattern matching algorithms
• Efficient comparison based string matching
• A fast string searching algorithm
• On the Exact Complexity of String Matching: Lower Bounds
• On the Exact Complexity of String Matching: Upper Bounds
• On the Worst-Case Behavior of String-Searching Algorithms
• Fast Pattern Matching in Strings
• Unnamed Item
• Unnamed Item

This page was built for publication: Tight comparison bounds for the string prefix-matching problem