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

DOI10.1016/0304-3975(95)00137-9MaRDI QIDQ671355zbMATH OpenOpenAlexFDO

Authors Livio Colussi, Laura Toniolo

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

class of compact orderspattern matching algorithmspattern preprocessingshift functionstring matchingtext search step

Mathematics Subject Classification ID

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

Recommendations

• String-matching on ordered alphabets
• Efficient comparison based string matching
• A unifying look at the Apostolico--Giancarlo string-matching algorithm
• On the Exact Complexity of String Matching: Upper Bounds

Cites work

• A comparison of three string matching algorithms
• A fast string searching algorithm
• Correctness and efficiency of pattern matching algorithms
• Design and implementation of an efficient priority queue
• Efficient comparison based string matching
• Fast Pattern Matching in Strings
• Fastest Pattern Matching in Strings
• scientific article; zbMATH DE number 432823 (Why is no real title available?)
• scientific article; zbMATH DE number 5542185 (Why is no real title available?)
• scientific article; zbMATH DE number 3811868 (Why is no real title available?)
• scientific article; zbMATH DE number 1256698 (Why is no real title available?)
• scientific article; zbMATH DE number 1142294 (Why is no real title available?)
• scientific article; zbMATH DE number 826052 (Why is no real title available?)
• On Simon's string searching algorithm
• On the computational power of pushdown automata
• On the Exact Complexity of String Matching: Upper Bounds
• String-matching on ordered alphabets
• The Boyer–Moore–Galil String Searching Strategies Revisited
• Tight comparison bounds for the string prefix-matching problem
• Time-space-optimal string matching
• 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

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