How the character comparison order shapes the shift function of on-line pattern matching algorithms

DOI10.1016/0304-3975(95)00137-9zbMath0874.68132OpenAlexW2083784516MaRDI QIDQ671355

Laura Toniolo, Livio Colussi

Publication date: 27 February 1997

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(95)00137-9

zbMATH Keywords

string matchingshift functionclass of compact orderspattern matching algorithmspattern preprocessingtext search step

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10) Combinatorics on words (68R15) Pattern recognition, speech recognition (68T10) Parallel algorithms in computer science (68W10)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On Simon's string searching algorithm
• Tight comparison bounds for the string prefix-matching problem
• Correctness and efficiency of pattern matching algorithms
• String-matching on ordered alphabets
• Efficient comparison based string matching
• Time-space-optimal string matching
• On the computational power of pushdown automata
• A fast string searching algorithm
• The Boyer–Moore–Galil String Searching Strategies Revisited
• A comparison of three string matching algorithms
• On the Exact Complexity of String Matching: Upper Bounds
• Design and implementation of an efficient priority queue
• Fast Pattern Matching in Strings
• Fastest Pattern Matching in Strings
• Two-way string-matching

This page was built for publication: How the character comparison order shapes the shift function of on-line pattern matching algorithms